Khi cập nhật 1 phần tử, chỉ có \(O(\log N)\) nút trên đường đi từ gốc đến lá bị thay đổi. Thay vì sửa trực tiếp, ta tạo bản sao của các nút đó và liên kết với các nút cũ.
Mỗi phiên bản là 1 cây nhị phân đầy đủ. Gốc của phiên bản \(v\) là root[v]. Khi truy vấn, duyệt từ root[v] xuống lá — tất cả nút trên đường đi đều tồn tại (nút mới hoặc nút cũ được liên kết).
#include<bits/stdc++.h>usingnamespacestd;structNode{intleft=-1,right=-1;// id nút con trái / phải (-1 = không có)longlongsum=0;// tổng đoạn mà nút này quản lý};vector<Node>tree;// kho chứa MỌI nút của mọi phiên bảnvector<int>roots;// roots[v] = id nút gốc của phiên bản v// Xây cây ban đầu (phiên bản 0) trên đoạn [lo, hi] - trả về id nút gốcintbuild(vector<int>&a,intlo,inthi){intid=tree.size();// id của nút sắp tạotree.push_back(Node());// đặt chỗ cho nút mớiif(lo==hi){tree[id].sum=a[lo];// lá: tổng = chính phần tửreturnid;}intmid=(lo+hi)/2;// chia đôi đoạntree[id].left=build(a,lo,mid);// xây con tráitree[id].right=build(a,mid+1,hi);// xây con phải// Tổng nút cha = tổng 2 contree[id].sum=tree[tree[id].left].sum+tree[tree[id].right].sum;returnid;}// Tạo phiên bản mới từ phiên bản có gốc `old`, gán a[pos] = val// Chỉ copy các nút trên đường đi từ gốc xuống lá pos, nút khác dùng chungintupdate(intold,intlo,inthi,intpos,longlongval){intid=tree.size();// id của nút mới sắp tạotree.push_back(tree[old]);// BƯỚC QUAN TRỌNG: copy nguyên nút cũ sang nút mớiif(lo==hi){tree[id].sum=val;// tới lá: ghi giá trị mớireturnid;}intmid=(lo+hi)/2;// chia đôi đoạnif(pos<=mid)// pos nằm bên trái: tạo nhánh trái mới, nhánh phải giữ nguyên (dùng chung)tree[id].left=update(tree[old].left,lo,mid,pos,val);else// pos nằm bên phải: tạo nhánh phải mới, nhánh trái giữ nguyêntree[id].right=update(tree[old].right,mid+1,hi,pos,val);// Tính lại tổng từ 2 con (1 con mới + 1 con dùng chung)tree[id].sum=tree[tree[id].left].sum+tree[tree[id].right].sum;returnid;// gốc của phiên bản mới}// Truy vấn tổng [l, r] trên cây có gốc `id` (tức 1 phiên bản cụ thể)longlongquery(intid,intlo,inthi,intl,intr){if(r<lo||hi<l)return0;// không giao nhau -> đóng góp 0if(l<=lo&&hi<=r)returntree[id].sum;// nằm trọn trong -> lấy luônintmid=(lo+hi)/2;// chia đôi để xuống 2 conreturnquery(tree[id].left,lo,mid,l,r)+query(tree[id].right,mid+1,hi,l,r);}intmain(){ios_base::sync_with_stdio(false);cin.tie(NULL);intn,q;cin>>n>>q;vector<int>a(n);for(inti=0;i<n;i++)cin>>a[i];roots.push_back(build(a,0,n-1));// phiên bản 0 = mảng ban đầuwhile(q--){inttype;cin>>type;if(type==1){intpos,val;cin>>pos>>val;pos--;// chuyển sang 0-index// Tạo phiên bản mới từ phiên bản gần nhất, rồi lưu gốc lạiintnewRoot=update(roots.back(),0,n-1,pos,val);roots.push_back(newRoot);}else{intver,l,r;cin>>ver>>l>>r;ver--;l--;r--;// chuyển sang 0-index// Truy vấn trên gốc của phiên bản ver (cây cũ vẫn nguyên vẹn)cout<<query(roots[ver],0,n-1,l,r)<<"\n";}}return0;}
importsysinput=sys.stdin.readlinesys.setrecursionlimit(1<<25)classNode:__slots__=['left','right','sum_val']def__init__(self,left=-1,right=-1,sum_val=0):self.left=leftself.right=rightself.sum_val=sum_valtree=[]roots=[]defbuild(a,lo,hi):# Xây cây ban đầu trên đoạn [lo, hi] - trả về id nút gốcnode_id=len(tree)# id của nút sắp tạotree.append(Node())# đặt chỗ cho nút mớiiflo==hi:tree[node_id].sum_val=a[lo]# lá: tổng = chính phần tửreturnnode_idmid=(lo+hi)//2# chia đôi đoạntree[node_id].left=build(a,lo,mid)# xây con tráitree[node_id].right=build(a,mid+1,hi)# xây con phải# Tổng nút cha = tổng 2 contree[node_id].sum_val=tree[tree[node_id].left].sum_val+tree[tree[node_id].right].sum_valreturnnode_iddefupdate(old,lo,hi,pos,val):# Tạo phiên bản mới từ nút gốc `old`, gán a[pos] = val# Chỉ copy nút trên đường đi xuống pos, nút khác dùng chungnode_id=len(tree)# id của nút mới sắp tạo# BƯỚC QUAN TRỌNG: copy nguyên nút cũ sang nút mớitree.append(Node(tree[old].left,tree[old].right,tree[old].sum_val))iflo==hi:tree[node_id].sum_val=val# tới lá: ghi giá trị mớireturnnode_idmid=(lo+hi)//2# chia đôi đoạnifpos<=mid:# pos bên trái: tạo nhánh trái mới, nhánh phải dùng chungtree[node_id].left=update(tree[old].left,lo,mid,pos,val)else:# pos bên phải: tạo nhánh phải mới, nhánh trái dùng chungtree[node_id].right=update(tree[old].right,mid+1,hi,pos,val)# Tính lại tổng từ 2 con (1 mới + 1 dùng chung)tree[node_id].sum_val=tree[tree[node_id].left].sum_val+tree[tree[node_id].right].sum_valreturnnode_id# gốc của phiên bản mớidefquery(node_id,lo,hi,l,r):# Truy vấn tổng [l, r] trên cây có gốc node_id (1 phiên bản cụ thể)ifr<loorhi<l:return0# không giao nhau -> đóng góp 0ifl<=loandhi<=r:returntree[node_id].sum_val# nằm trọn trong -> lấy luônmid=(lo+hi)//2# chia đôi để xuống 2 conreturnquery(tree[node_id].left,lo,mid,l,r)+query(tree[node_id].right,mid+1,hi,l,r)n,q=map(int,input().split())a=list(map(int,input().split()))roots.append(build(a,0,n-1))# phiên bản 0 = mảng ban đầufor_inrange(q):parts=list(map(int,input().split()))ifparts[0]==1:pos,val=parts[1]-1,parts[2]# chuyển sang 0-index# Tạo phiên bản mới từ phiên bản gần nhất, lưu gốc lạinew_root=update(roots[-1],0,n-1,pos,val)roots.append(new_root)else:ver,l,r=parts[1]-1,parts[2]-1,parts[3]-1# 0-index# Truy vấn trên gốc phiên bản ver (cây cũ vẫn nguyên vẹn)print(query(roots[ver],0,n-1,l,r))
SAI — Quên push_back(tree[old]): Nếu trong update bạn sửa trực tiếp tree[old].sum = ... thay vì copy sang nút mới, phiên bản cũ bị phá hủy → truy vấn lịch sử sai. Luôn copy trước khi sửa:
// SAI: tree[old].sum = val; // phá phiên bản cũ!// ĐÚNG:intid=tree.size();tree.push_back(tree[old]);// copy rồi mới sửa tree[id]
SAI — Cấp phát thiếu nút (tràn nodes): Mỗi update tạo \(O(\log N)\) nút, \(Q\) truy vấn cần \(N \times 4 + Q \times 20\) nút (với \(N, Q \le 10^5\) cần ~2 triệu nút). Nếu khai báo mảng tĩnh quá nhỏ → tràn, crash. Dùng vector<Node> tree; tree.reserve(4000005); hoặc cấp phát động.
SAI — Nhầm chỉ số phiên bản (ver--): Đề thường đánh số phiên bản từ 1, code lưu roots[0] = phiên bản 1. Quên ver-- (hoặc trừ 2 lần) → truy vấn nhầm phiên bản. Quy ước rõ: roots[0] là mảng ban đầu, mỗi type 1 push thêm 1 gốc; khi đọc ver từ input (1-indexed) thì ver-- đúng 1 lần.
