| 12345 |
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Node{int l=0,r=0;long long sum=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<long long>a(n);for(auto&x:a)cin>>x;vector<Node>tr(1);tr.reserve(4*n+q*20);auto build=[&](auto&&self,int l,int r)->int{int u=tr.size();tr.push_back({});if(l==r){tr[u].sum=a[l];return u;}int m=(l+r)/2;tr[u].l=self(self,l,m);tr[u].r=self(self,m+1,r);tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;return u;};auto upd=[&](auto&&self,int old,int l,int r,int p,long long x)->int{int u=tr.size();tr.push_back(tr[old]);if(l==r){tr[u].sum=x;return u;}int m=(l+r)/2;if(p<=m)tr[u].l=self(self,tr[old].l,l,m,p,x);else tr[u].r=self(self,tr[old].r,m+1,r,p,x);tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;return u;};auto ask=[&](auto&&self,int u,int l,int r,int ql,int qr)->long long{if(ql<=l&&r<=qr)return tr[u].sum;int m=(l+r)/2;long long s=0;if(ql<=m)s+=self(self,tr[u].l,l,m,ql,qr);if(qr>m)s+=self(self,tr[u].r,m+1,r,ql,qr);return s;};vector<int>root{build(build,0,n-1)};while(q--){int type,k;cin>>type>>k;--k;if(type==1){int p;long long x;cin>>p>>x;root[k]=upd(upd,root[k],0,n-1,p-1,x);}else if(type==2){int l,r;cin>>l>>r;cout<<ask(ask,root[k],0,n-1,l-1,r-1)<<'\n';}else root.push_back(root[k]);}}
|
