ACM大牛总结的线段树专辑,超经典的

1、完全版】线段树很早前写的那篇线段树专辑至今一直是本博客阅读点击量最大的一片文章,当时觉得挺自豪的,还去pku打广告，但是现在我自己都不太好意思去看那篇文章了，觉得当时的代码风格实在是太丑了,很多线段树的初学者可能就是看着这篇文章来练习的,如果不小心被我培养出了这么糟糕的风格,实在是过意不去,正好过几天又要给集训队讲解线段树,所以决定把这些题目重新写一遍,顺便把近年我接触到的一些新题更新上去并且学习了splay等更高级的数据结构后对线段树的体会有更深了一层,线段树的写法也就比以前飘逸,简洁且方便多了.在代码前先介绍一些我的线段树风格:maxn是题目给的最大区间，而节点数要开4倍,确切的来说节点数

2、要开大于maxn的最小2x的两倍Ison和rson分辨表示结点的左儿子和右儿子，由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示以前的写法是另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行，只需要写函数的时候多两个参数，结合Ison和rson的预定义可以很方便PushUP(intrt)是把当前结点的信息更新到父结点PushDown(intrt)是把当前结点的信息更新给儿子结点rt表示当前子树的根(root)，也就是当前所在的结点整理这些题目后我觉得线段树的题目整体上可以分成以下四个部分:单点更新最最基础的线段树，只更新叶子节点,然后把信

3、息用PushUP(intr)这个函数更新上来ohdu1166敌兵布阵题意:0(-1)思路:0(-1)线段树功能:update:单点增减query:区间求和?ViewCodeCPP#incIude2#defineIsonI,m,rt1#definersonm+1,r,rt1|1constintmaxn=55555;intsummaxn2;voidPushUP(intrt)sumrt=sumrt1+sumrt1;build(lson);build(rson);PushUP(rt);voidupdate(intp,intadd,intl,intr,intrt)if(l=r)sumrt+=add;re

4、turn;intm=(l+r)1;if(p=m)update(p,add,lson);elseupdate(p,add,rson);PushUP(rt);intquery(intL,intR,intl,intr,intrt)if(L=l&r1;intret=0;if(Lm)ret+=query(L,R,rson);returnret;intmain()intT,n;scanf(%d,&T);for(intcas=1;cas=T;cas+)printf(Case%d:n,cas);scanf(%d,&n);build(1,n,1);charop10;while(scanf(%s,op)if(op

5、0=E)break;inta,b;scanf(%d%d,&a,&b);if(op0=Q)printf(%dn,query(a,b,1,n,1);elseif(op0=S)update(a,-b,1,n,1);elseupdate(a,b,1,n,1);1415161718192021222324252627282930313233343536373839404142434445464748495051525354555657return0;58581234567891011121314151617181920212223242526272829303132333435363738ohdu175

6、4IHateIt题意:0(-1)思路:0(-1)线段树功能:update:单点替换query:区间最值?ViewCodeCPP#include#includeusingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|1constintmaxn=222222;intMAXmaxn2;voidPushUP(intrt)MAXrt=max(MAXrt1,MAXrt1;build(lson);build(rson);PushUP(rt);voidupdate(intp,intsc,intl,intr,intrt)if(l=r)MAXrt=sc;r

7、eturn;intm=(l+r)1;if(p=m)update(p,sc,lson);elseupdate(p,sc,rson);PushUP(rt);intquery(intL,intR,intl,intr,intrt)if(L=l&r1;lson);intret=0;if(Lm)ret=max(ret,query(L,R,rson);40returnret;4142intmain()43intn,m;44while(scanf(%d%d,&n,&m)45build(1,n,1);46while(m-)47charop2;48inta,b;49scanf(%s%d%d,op,&a,&b);5

8、0if(op0=Q)printf(%dn,query(a,b,1,n,1);51elseupdate(a,b,1,n,1);525354return0;55ohdu1394MinimumInversionNumber题意:求Inversion后的最小逆序数思路:用0(nlogn)复杂度求出最初逆序数后，就可以用0(1)的复杂度分别递推出其他解线段树功能:update:单点增减query:区间求和?ViewCodeCPP#include#includeusingnamespacestd;4#definelsonl,m,rt1#definersonm+1,r,rt1|1constintmaxn=5

9、555;intsummaxn2;voidPushUP(intrt)10sumrt=sumrt1+sumrt1;build(lson);17build(rson);18voidupdate(intp,intl,intr,intrt)if(l=r)return;intm=(l+r)1;if(p=m)update(p,lson);elseupdate(p,rson);PushUP(rt);query(intL,intR,intl,intr,intrt)if(L=l&r1;intret=0;if(Lm)ret+=query(L,R,rson);returnret;xmaxn;main()intn;wh

10、ile(scanf(%d,&n)build(0,n-1,1);intsum=0;for(inti=0;in;i+)scanf(%d,&xi);sum+=query(xi,n-1,0,n-1,1);update(xi,0,n-1,1);intret=sum;for(inti=0;in;i+)sum+=n-xi-xi-1;ret=min(ret,sum);printf(%dn,ret);return0;ohdu2795Billboard题意:h*w的木板，放进一些1*L的物品，求每次放空间能容纳且最上边的位子思路:每次找到最大值的位子，然后减去L线段树功能:query:区间求最大值的位子（直接把u

11、pdate的操作在query里做了）?ViewCodeCPP1#include2223242526272829int30313233343536373839int40int4142434445464748495051525354555657582#include1);21sumrt+;3456789101112131415161718192021222324252627282930313233343536373839404142usingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|1constintmaxn=222222;inth,w

12、,n;intMAXmaxn2;voidPushUP(intrt)MAXrt=max(MAXrt1,MAXrt1;build(lson);build(rson);intquery(intx,intl,intr,intrt)if(l=r)MAXrt-=x;returnl;,rson);intm=(l+r)1;intret=(MAXrt=x)?query(x,lson):query(xPushUP(rt);returnret;intmain()while(scanf(%d%d%d,&h,&w,&n)if(hn)h=n;build(1,h,1);while(n-)intx;scanf(%d,&x);i

13、f(MAX1x)puts(-1);elseprintf(%dn,query(x,1,h,return0;练习:poj2828BuyTicketspoj2886WhoGetstheMostCandies?1);21sumrt+;成段更新（通常这对初学者来说是一道坎）,需要用到延迟标记（或者说懒惰标记）,简单来说就是每次更新的时候不要更新到底，用延迟标记使得更新延迟到下次需要更新or询问到的时候ohdu1698JustaHook题意:0（-1）思路:0（-1）线段树功能:update:成段替换（由于只query次总区间，所以可以直接输出1结点的信息）?ViewCodeCPP1#include2#i

14、nclude3usingnamespacestd;45#definelsonl,m,rt16#definersonm+1,r,rt1|17constintmaxn=111111;8inth,w,n;9intcolmaxn2;10intsummaxn2;11voidPushUp(intrt)12sumrt=sumrt1+sumrt1|1;1314voidPushDown(intrt,intm)15if(colrt)16colrt1=colrt1|1=colrt17sumrt1)*colrt;18sumrt1)*colrt;19colrt=0;202122voidbuild(intl,intr,i

15、ntrt)23colrt=0;24sumrt=1;25if(l=r)return;26intm=(l+r)1;27build(lson);28build(rson);29PushUp(rt);3031voidupdate(intL,intR,intc,intl,intr,intrt)32if(L=l&r1;39if(Lm)update(L,R,c,rson);PushUp(rt);4243intmain()1113141617111314161721sumrt+;444546474849505152intT,n,m;scanf(%d,&T);for(intcas=1;cas=T;cas+)sc

16、anf(%d%d,&n,&m);build(1,n,1);while(m-)inta,b,c;scanf(%d%d%d,&a,&b,&c);update(a,b,c,1,n,1);5354printf(Case%d:Thetotalvalueofthehookis%d.n,cassum1);5556return0;57opoj3468ASimpleProblemwithIntegers题意:0(-1)思路:0(-1)线段树功能:update:成段增减query:区间求和?ViewCodeCPP#include#includeusingnamespacestd;4#definelsonl,m,r

17、t1#definersonm+1,r,rt1|1#defineLLlonglongconstintmaxn=111111;10LLaddmaxn2;LLsummaxn2;voidPushUp(intrt)12sumrt=sumrt1+sumrt1|1;15voidPushDown(intrt,intm)if(addrt)1113141617111314161721sumrt+;addrt1+=addrt;addrt1);1);21sumrt+;18sumrt19sumrt120addrt=0;212223voidbuild(intl,intr,intrt)24addrt=0;25if(l=r)

18、26scanf(%lld,&sumrt);27return;2829intm=(l+r)1;30build(lson);31build(rson);32PushUp(rt);3334voidupdate(intL,intR,intc,intl,intr,intrt)35if(L=l&r1;42if(L=m)update(L,R,c,lson);43if(mR)update(L,R,c,rson);44PushUp(rt);4546LLquery(intL,intR,intl,intr,intrt)47if(L=l&r1;52LLret=0;53if(L=m)ret+=query(L,R,lso

19、n)54if(mR)ret+=query(L,R,rson);55returnret;5657intmain()58intN,Q;59scanf(%d%d,&N,&Q);60build(1,N,1);61while(Q-)13intcnt;13intcnt;62charop2;63inta,b,c;64scanf(%s,op);65if(op0=Q)66scanf(%d%d,&a,&b);67printf(%lldn,query(a,b,68else69scanf(%d%d%d,&a,&b,&c);70update(a,b,c,1,N717273return0;74poj2528Mayorsp

20、osterso1,N,1);,1);题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报思路:这题数据范围很大,直接搞超时+超内存,需要离散化:离散化简单的来说就是只取我们需要的值来用,比如说区间1000,2000,1990,2012我们用不到卜，9991001,1991991,19992001,20112013,+这些值，所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了所以离散化要保存所有需要用到的值,排序后，分别映射到1n,这样复杂度就会小很多很多而这题的难点在于每个数字其实表示的是一个单位长度（并且一个点）,这样普

21、通的离散化会造成许多错误（包括我以前的代码,poj这题数据奇弱）给出下面两个简单的例子应该能体现普通离散化的缺陷:1-101-45-101-101-46-10为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说1,2,6,10如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成1,2,3,6,7,10,然后再做线段树就好了.线段树功能:update:成段替换query:简单hash?ViewCodeCPP#include#include#includeusingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|17consti

22、ntmaxn=11111;boolhashmaxn;intlimaxn,rimaxn;intXmaxn*3;intcolmaxn4;1415voidPushDown(intrt)16if(colrt!=-1)17colrt1=colrt1|1=18colrt=-1;192021voidupdate(intL,intR,intc,intl,intr,intrt22if(L=l&r1;28if(L=m)update(L,R,c,lson29if(m1;39query(lson);40query(rson);4142intBin(intkey,intn,intX)43intl=0,r=n-1;44w

23、hile(l1;46if(Xm=key)returnm;47if(Xmkey)l=m+1;48elser=m-1;4950return-1;5152intmain()53intT,n;54scanf(%d,&T);55while(T-)56scanf(%d,&n);colrt;5757585960616263646566676869707172737475767778798081828384return0;intnn=0;for(inti=0;in;i+)scanf(%d%d,&lii,&rii);Xnn+=lii;Xnn+=rii;sort(X,X+nn);intm=1;for(inti=1

24、;i0;i-)if(Xi!=Xi-1+1)Xm+=Xi-1+1;sort(X,X+m);memset(col,-1,sizeof(col);for(inti=0;in;i+)intl=Bin(lii,m,X);intr=Bin(rii,m,X);update(l,r,i,0,m,1);cnt=0;memset(hash,false,sizeof(hash);query(0,m,1);printf(%dn,cnt);opoj3225HelpwithIntervals题意:区间操作,交,并,补等思路:我们一个一个操作来分析:（用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含）U:把区间

25、l,r覆盖成1I：把卜,l）（r,覆盖成0D:把区间l,r覆盖成0C:把卜,l）（r,覆盖成0,且l,r区间0/1互换S:l,r区间0/1互换成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了所以当一个节点得到覆盖标记时把异或标记清空123456789101112131415161718192021222324252627282930313233343536373839而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记开区间闭区

26、间只要数字乘以2就可以处理（偶数表示端点,奇数表示两端点间的区间）线段树功能:update:成段替换，区间异或query:简单hash?ViewCodeCPP#include#include#include#includeusingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|1constintmaxn=131072;boolhashmaxn;intcovermaxn2;intXORmaxn2;voidFXOR(intrt)if(coverrt!=-1)coverrt人=1；elseX0Rrt人=1;voidPushDown(intrt

27、)coverrt;if(coverrt!=-1)coverrt1=coverrt1|1=XORrt1=XORrt1|1=0;coverrt=-1;if(XORrt)FXOR(rt1);FXOR(rt1|1);XORrt=0;voidupdate(charop,intL,intR,intl,intr,intrt)if(L=l&r1;if(L=m)update(op,L,R,lson);elseif(op=I|op=C)XORrt1=coverrt1=0;if(mR)update(op,L,R,rson);elseif(op=I|op=C)XORrt1|1=coverrt1|1=0;voidque

28、ry(intl,intr,intrt)if(coverrt=1)for(intit=l;it1;query(lson);query(rson);intmain()cover1=XOR1=0;charop,l,r;inta,b;while(scanf(%c%c%d,%d%cn,&op,&l,&a,&b,&r)a=1,bb)if(op=C|op=I)cover1=XOR1=0;elseupdate(op,a,b,0,maxn,1);query(0,maxn,1);boolflag=false;40414243444546474849505152535455565758596061626364656

29、66768697071727374757677787980818283ints=-1,e;for(inti=0;i1,92(e+1)1,e&1?):);93s=-1;94959697if(!flag)printf(emptyset);98puts();99return0;练习:opoj1436HorizontallyVisibleSegmentsopoj2991CraneoAnotherLCISoBracketSequence区间合并这类题目会询问区间中满足条件的连续最长区间，所以PushUp的时候需要对左右儿子的区间进行合并opoj3667Hotel题意:1a:询问是不是有连续长度为a的空房

30、间，有的话住进最左边ab:将a,a+b-1的房间清空思路:记录区间中最长的空房间线段树操作:update:区间替换query:询问满足条件的最左断点?ViewCodeCPP#include#include#include#includeusingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|189constintmaxn=55555;intlsummaxn2,rsummaxn2,msummaxn2;intcovermaxn2;12131415161718192021222324252627282930313233343536373839

31、4041424344454647484950515253545556voidPushDown(intrt,intm)if(coverrt!=-1)coverrt1=coverrt1|1=coverrt;msumrt1=lsumrt1=rsumrt1);msumrt1|1=lsumrt1|1=rsumrt1);coverrt=-1;voidPushUp(intrt,intm)lsumrt=lsumrt1;rsumrt=rsumrt1)lsumrt+=lsumrt1)rsumrt+=rsumrt1;msumrt=max(lsumrt1|1+rsumrt1,max(msumrt1,msumrt1;b

32、uild(lson);build(rson);voidupdate(intL,intR,intc,intl,intr,intrt)if(L=l&r1;if(L=m)update(L,R,c,lson);if(m1;if(msumrt=w)returnquery(w,lson);elseif(rsumrt1+lsumrt=w)returnm-rsumrt1+1;57returnquery(w,rson);5859intmain()60intn,m;61scanf(%d%d,&n,&m);62build(1,n,1);63while(m-)64intop,a,b;65scanf(%d,&op);6

33、6if(op=1)67scanf(%d,&a);68if(msum1a)puts(0);69else70intp=query(a,1,n,1);71printf(%dn,p);72update(p,p+a-1,1,1,7374else75scanf(%d%d,&a,&b);76update(a,a+b-1,0,1,n,1);77,1);return0;练习:ohdu3308LCISohdu3397Sequeneeoperationohdu2871MemoryControlohdu1540TunnelWarfareoCF46-DParkingLot扫描线这类题目需要将一些操作排序,然后从左到右用

34、一根扫描线（当然是在我们脑子里）扫过去最典型的就是矩形面积并，周长并等题ohdu1542Atlantis题意:矩形面积并思路:浮点数先要离散化;然后把矩形分成两条边，上边和下边，对横轴建树，然后从下到上扫描上去，用ent表示该区间下边比上边多几个线段树操作:update:区间增减query:直接取根节点的值?ViewCodeCPP#include#include#include#includeusingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|1constintmaxn=2222;intcntmaxn2;doublesummaxn2

35、;doubleXmaxn;structSegdoubleh,l,r;ints;Seg()Seg(doublea,doubleb,doublec,intd):l(a),r(b),h(c),s(d)booloperator(constSeg&cmp)constreturnhcmp.h;ssmaxn;voidPushUp(intrt,intl,intr)if(cntrt)sumrt=Xr+1-Xl;elseif(l=r)sumrt=0;elsesumrt=sumrt1+sumrt1|1;voidupdate(intL,intR,intc,intl,intr,intrt)if(L=l&r1;if(L=

36、m)update(L,R,c,lson);if(mR)update(L,R,c,rson);PushUp(rt,l,r);intBin(doublekey,intn,doubleX)intl=0,r=n-1;while(l1;if(Xm=key)returnm;if(Xmkey)l=m+1;elser=m-1;return-1;56789101112131415161718192021222324252627282930313233343536373839404142434445464748intmain()8849intn,cas=1;50while(scanf(%d,&n)&n)51int

37、m=0;52while(n-)53doublea,b,c,d;54scanf(%lf%lf%lf%lf,&a,&b,&c,&d);55Xm=a;56ssm+=Seg(a,c,b,1);57Xm=c;58ssm+=Seg(a,c,d,-1);5960sort(X,X+m);61sort(ss,ss+m);62intk=1;63for(inti=1;im;i+)64if(Xi!=Xi-1)Xk+=Xi;6566memset(cnt,0,sizeof(cnt);67memset(sum,0,sizeof(sum);68doubleret=0;69for(inti=0;im-1;i+)70intl=B

38、in(ssi.l,k,X);71intr=Bin(ssi.r,k,X)-1;72if(l=r)update(l,r,ssi.s,73ret+=sum1*(ssi+1.h-ssi.h);7475printf(Testcase#%dnTotalexploredarea:%.2lfnn7677return0;780,k,cas+ohdu1828Picture题意:矩形周长并思路:与面积不同的地方是还要记录竖的边有几个（numseg记录），并且当边界重合的时候需要合并（用lbd和rbd表示边界来辅助）线段树操作:update:区间增减query:直接取根节点的值?ViewCodeCPP1,1);ret);#include#include#include#includeusingnamespacestd;#definelsonl,m,rt1#definersonm+1,r,rt1|1910111213141516171819202122232425262728293031323334353637383940414243444546474849505152constintmaxn=22222;structSegintl