可持久化线段树总结

1、可持久化线段树的总结by石门中学柯新宇可持久化线段树，说白了，就是具有一个个时间的树链。因为修改单点，只会对树上的一条链发生改变，我们只需记录更改过的树链即可。我们可以发现，每次修改单点时，只会影响到一条链，只需把链 存起来就行了。我才用的方法是：对于每一次修改，开一个root，记录树根。（用 指针类型，写起来比较方便）struct nodelong long s,d; node *left,*right;tree(max n 5)+(max n 3),*rootmax n;node *newno de()t0+; treetO.s二treetO.d=O;treetO.left二treetO.

2、right二tree;return tree+tO;root0=newnode();for(int i=1;i=ti;i+) rooti=newnode();for(int i=1;id+;ro-s+=v;return;int mid=(L+R)1;node *yy=newnode(); / 新开节点 if(xleft; / 拷贝原来的信息ro-left=yy; / 将新的节点连给父亲结点 updata(ro-left,L,mid,x,v); else*yy=*ro-right;ro-right=yy; updata(ro-right,mid+1,R,x,v);ro-s=ro-left-s+r

3、o-right-s; /up 操作 ro-d=ro-left-d+ro-right-d;至于，区间修改，开个懒惰标记记一记就好了，不用每次更新都 下发标记(这样会爆空间的) ，查询的时候加上祖先的标记就好了。有几道比较经典的题，可以用来练练手： 先把可持久化线段树模板练熟了，做题会事半功倍。因为这都是“套路”Bzoj2588-比较麻烦，离散化加 lea 加 query(r1,r2,r3,r4,1,n,)Bzoj2809离散化Hdu5919Hdu4348Bzoj2809代码：#include#include#define imin(a,b) (ab)?a:b)#define maxn 10005

4、0using namespace std;int n,m,t0,ti;long long ans;int famaxn,llmaxn;long long cctmaxn;struct aaaaint l,r,d; tmmaxn;struct nodelong long s,d; node *left,*right; tree(maxn5)+(maxn3),*rootmaxn;struct eeeeint fa,pi; long long ci,li; masmaxn; int hmaxn,d0;struct dataint to,next; dmaxn;node *newnode()t0+;

5、treet0.s=treet0.d=0;treet0.left=treet0.right=tree;return tree+t0;bool cmp(int A,int B)return (masA.ci0;p=dp.next) dfs(dp.to);tmyu.r=ti;void updata(node *ro,int L,int R,int x,long long v)if(L=R)ro-d+;ro-s+=v;return; int mid=(L+R)1;node *yy=newnode();if(xleft;ro-left=yy;updata(ro-left,L,mid,x,v); else

6、*yy=*ro-right;ro-right=yy;updata(ro-right,mid+1,R,x,v); ro-s=ro-left-s+ro-right-s; ro-d=ro-left-d+ro-right-d;long long query(node *r1,node *r2,int L,int R,long long M)if(L=R) return imin(r2-d-r1-d),M/cctL); if(r2-s-r1-sd-r1-d;long long xx=r2-left-s-r1-left-s;int mid=(L+R)1;if(xx=M) return query(r1-l

7、eft,r2-left,L,mid,M); else return(r2-left-d-r1-left-d+query(r1-right,r2-right,mid+1,R,M-xx); int main()scanf(%d%d,&n,&m);mas0.li=0; ti=0;tree0.left=tree0.right=tree;for(int i=1;i=n;i+) scanf(%d%lld%lld,&masi.fa,&masi.ci,&masi.li); lli=i; addedge(masi.fa,i);sort(ll+1,ll+1+n,cmp);int last=-1,y0=0;for(

8、int i=1;i=n;i+)if(last!=maslli.ci)y0+; last=maslli.ci;ccty0=maslli.ci;maslli.pi=y0;ti=-1;dfs(0);root0=newnode();for(int i=1;i=ti;i+) rooti=newnode();for(int i=1;i=ti;i+)*rooti=*rooti-1;updata(rooti,1,y0,mastmi.d.pi,mastmi.d.ci);ans=0;for(int i=1;ians)?num*mastmi.d.li:ans;printf(%lldn,ans);4408: Fjoi

9、 2016神秘数Time Limit: 10 Sec Memory Limit: 128 MB一个可重复数字集合S的神秘数定义为最小的不能被 S的子集的和表示的正整数。例如 S=1,1,1,4,13，1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18无法表示为集合S的子集的和，故集合S的神秘数为&现给定 n 个正整数 a1.an ， m 个询问，每次询问给定一个区间l,r(lv=r)，求由al,al+1,ar所构成的可重复数字集合的神秘数。Input第一行一个整数n表示数字个数。第二行 n 个整数，从 1 编号。第三行一个整数m,表示询

10、问个数。以下m行，每行一对整数l,r，表示一个询问。Output对于每个询问,输出一行对应的答案。Sample Input51 2 4 9 1051 11 21 31 41 5Sample Output24888对于 100%的数据点，n,m = 100000,刀 ai = 10八9注：很有趣的题，建议不要一开始就看题解，仔细想一想。AC代码:#include#include#define maxn 100050#define For(a,b,c) for(int a=b;a=c;a+)using namespace std;int n,m0,m,t0;int dmaxn,mpmaxn;str

11、uct datadata *left,*right;int sum; tree80*maxn,*rootmaxn;bool cmp(int a,int b)return (dax | Rsum+=vv;return;int mid=(L+R)1;data *yy=newnode();if(xleft;ro-left=yy;updata(ro-left,L,mid,x,vv); else*yy=*ro-right;ro-right=yy; updata(ro-right,mid+1,R,x,vv);ro-sum=ro-left-sum+ro-right-sum;int query(data *r

12、1,data *r2,int L,int R,int li,int ri)if(liR | riL) return 0;if(li=L & Rsum-r1-sum);int mid=(L+R)1;int x1=query(r1-left,r2-left,L,mid,li,ri);int x2=query(r1-right,r2-right,mid+1,R,li,ri);return (x1+x2);int main()scanf(%d,&n);For(i,1,n) scanf(%d,&di),mpi=i;dn+1=1e9;sort(mp+1,mp+1+n,cmp);int oi=0,p=0;For(i,1,n)oi=(pdmpi)?oi+1:oi;p=dmpi;mpi=oi;m0=oi;scanf(%d,&m);tree0.left=tree0.right=tree;for(int i=1;i=n;i+) rooti=newnode();root0=&tree0;For(ti,1,n)*rootti=*rootti-1;updata(rootti,1,m0,mpti,dti);For(i,1,m)int ll,rr;scanf(%d%d,&ll,&rr);int lose=1,he=0;for(;)int l=0,r=n+1;while(l+11;if(dmm=lose) l=m