2014pku acm线段和树状数组实际上还是称为区间更好理解一些

暑期课《ACM/ICPC竞赛信息 课程网页 线段树和树状数信息线段树(Interval 点表示了一个区间[a。,通常是整数。长度为1][a,(a+b)/]，右儿子表示的区间为[(a+b)/2+1,b](法去尾取整）区间[1,区间[1,9] 834567983456791212别是[a,(a+b)/2]和a+b)/2+1,b（除法去尾取整点对应的区间是[a,b],那么它的深度为log2(b-a+11(向上则线段树总结点数目为2N-区间[1,9]的线段树上，区间[2,8]

区间[1,区间[1,9]的线段树上，区间[2,8] 834567983456791212 XXXXXX XXXXXX线段树的1、线段树的深度不超过log2(n)+1（向上取整，n是根节 function以节点v为根建树、v对应区间为{对节点v初始if{以v的左孩子为根建树、区间为以v的右孩子为根建树、区间为}}线段树应用1、对序列 希望第2个操作每次能在log(n)时间内完线段树应用用线段树解题，关键是要想清楚每个节点要存哪以及这些信息如何高效更新，，查询。不要一更新就更新到叶子节点，那样更新效率就可能变成O(n)先建树，然后数据，然例题POJ3264Balanced给定Q(1Q200,000)个数A1,A2多次求任一区间Ai–Aj中最大数和最小差本题树节点结构是什么例题POJ3264Balanced给定Q(1Q200,000)个数A1,A2多次求任一区间Ai–Aj中最大数和最小差本题树节点结构struct{intL,R//区间起点和CNode*pLeft,*pRight;左子节点下标为i右子节点下标为如果用一维数组存放线段树，且根节点区间使用左右节点指针，则数组需要有2n-1个元 2*2^[log2n]-14n1实际运用时常可以更小,可尝试3nSample63//6个数，3次个查2

Sample630#include<iostream>usingnamespacestd;constintINF=0xffffff0;intminV=INF;intmaxV=-structNode//{intL,intMid(){return}Nodetree[800010//4voidBuildTree(introot,intL,int{tree[root].L=L;tree[root].R=R;tree[root].minV=INF;tree[root].maxV=-INF;if(L!=R){BuildTree(2*root+2,(L+R)/2+1,}}voidInsert(introot,inti,int {if(tree[root].L==tree[root].R)//tree[root].R==itree[root].minVtree[root].maxVv;}tree[root].minV=min(tree[root].minV,v);tree[root].maxV=max(tree[root].maxV,v);if(i<=tree[root].Mid())}

voidQuery(introot,ints,int{if(tree[root].minV>=minV&&tree[root].maxV<=maxVif(tree[root].L==s&&tree[root].R==e){minV=min(minV,tree[root].minV);maxV=max(maxV,tree[root].maxV);return;}if(e<=elseif(s>tree[root].Mid()else}}

int{intinti,j,k;for(i=1;i<=n;i++)}for(i=0;i<q;i++)intminV=INF;maxV=-printf("%d\n",maxV-}return}POJ3468ASimpleProblemwith给定Q(1Q100,000)个数A1,A2以及可能多次进行的两个操作对某个区间Ai…Aj的每个数都加n(n）求某个区间Ai…Aj的数的POJ3468ASimpleProblemwith本题树节点结构struct{intLCNode*pLeft,*pRight;longlongnSum;//原来的和longlongInc//增量c的累加};POJ3468ASimpleProblemwith节点，则增加其节点的Inc值，不再往下，接下来再往下查询。Inc往下带的过程也是

假设开始A1A9都是

33

991212

(0,0) A1… 1212

39[1,39[1, (0,0) 查A2[1,[1,1212

39 39 (0,0) 1212

39 39 (0,2) 查A2

33

2

991212

(0,2)

查A2

4 23 23

2

9912122

(0,2)

#include<iostream>usingnamespacestd;structCNode{intLCNode*pLeft,*pRight;longlongnSum;//原来的和longlongInc//增量c的累加intnCount=intMid(CNode*{return(pRoot->L+pRoot-}voidBuildTree(CNode*pRoot,intL,int{pRoot->L=L;pRoot->R=R;pRoot->nSum=0;pRoot->Inc=if(L==nCountpRoot->pLeft=Tree+nCountpRoot->pRight=Tree+nCount;}voidInsert(CNode*pRoot,inti,int{if(pRoot->L==i&&pRoot->R==i)pRoot->nSum=v;return;}pRoot->nSum+=if(i<=}

voidAdd(CNode*pRoot,inta,intb,longlong{if(pRoot->L==a&&pRoot->R==b)pRoot->Inc+=return}pRoot->nSum+=c*(b-a+1)if(b<=(pRoot->L+pRoot-elseif(a>=(pRoot->L+pRoot->R)/2else(pRoot->L+pRoot->R)/2(pRoot->L+pRoot->R)/2+}}longlongQuerynSum(CNode*pRoot,inta,int{if(pRoot->L==a&&pRoot->R==(pRoot->R-pRoot->L+1)*pRoot->IncpRoot->nSum+=(pRoot->R-pRoot->L+1)*pRoot->Inc;Add(pRoot->pLeft,pRoot->L,Mid(pRoot),pRoot->Inc);pRoot->Inc=if(b<=returnQuerynSum(pRoot-elseif(a>=Mid(pRoot)+returnQuerynSum(pRoot-else}}

returnQuerynSum(pRoot->pLeft,a,Mid(pRoot))QuerynSum(pRoot->pRight,Mid(pRoot)+int{intcharcmd[10];inti,j,k;nCount=0;for(i=1;i<=n;i++){}for(i=0;i<q;i++)if(cmd[0]=='C')Add(}return}

else}

,POJ2528Mayor's给定一些海报，可能互相，告诉你每序，问没有被完全盖住的海报有POJ2528Mayor's我们只要对这19,999个区间，然后建树即POJ2528Mayor's 张海报覆盖的单位区间[a,b海报覆盖了从a号关键：数据的顺 从上往下次每张海报，这样后的海报不可能覆盖先的海报，因此一张海报时间复杂度nlognn为海报数目POJ2528Mayor'sPOJ2528Mayor'sstruct{intboolCNode*pLeft,*#include<iostream>#include<algorithm>#include<math.h>usingnamespacestd;intn;struct{intCPostintx[20200//struct{intCNode*pLeft,*intnNodeCount=0;intMid(CNode*{return(pRoot->L+pRoot-}voidBuildTree(CNode*pRoot,intL,int{pRoot->L=pRoot->R=pRoot->bCovered=if(L==RpRoot->pLeft=Tree+nNodeCount;nNodeCount++;pRoot->pRight=Tree+nNodeCount;BuildTree(pRoot->pLeft,L,(L+R)/2);BuildTree(pRoot->pRight,(L+R)/2+1,R);}boolPost(CNode*pRoot,intL,int{ 一张正好覆盖区间[L,R]的海报,返回true则说明区间[L,R]是部分全部可if(pRoot->bCovered) returnfalse;if(pRoot->L==L&&pRoot->R==R){return}boolbResultif(R<=Mid(pRoot)bResult=Post(pRoot->pLeft,L,R);elseif(L>=Mid(pRoot)+1)bResult=Post(pRoot-else}

boolb1=Post(pRoot->pLeftboolb2=Post(pRoot->pRight,Mid(pRoot)+1,R);bResult=b1||b2;//要更新根节点的覆盖pRoot->bCovered=true;returnbResult;}int{intinti,j,k;intnCaseNo=0;while(t--){nCaseNo++;intnCount=0;for(i=0;i<n;i++)scanf("%d%d",&&posters[i].Rx[nCount++]=x[nCount++]=}nCountunique(x,x+nCount)x//去掉重复元//下面离散intnIntervalNo=for(i=0;i<nCount;i++)hash[x[i]]=if(i<nCount-1)if(x[i+1]-x[i]==nIntervalNo}}

nIntervalNo+=intnSum=0;forin1;i0;i从后往前看每个海报是 if(nSum}return}

点数，可能互相，问这些矩形覆盖到用线段树做，先要离散 个个矩形线段树？过程中这些信随着扫描线的右移动，覆盖面积不断增struct{intCNode*pLeft,*doubleLen//当前,本区间上有多长的intCovers;//本区间当前被多少个完全包一开始，所有Len0Covers数据的顺些纵边线段树。要记住哪些纵边是一个的右边（结束边），时，对Len和增量是Len*本边到下一条边的距#include<iostream>#include<math.h>#include<set>usingnamespacestd;doubley[210];struct{intCNode*pLeft,*struct{double}intnNodeCount=booloperator<(constCLine&l1,constCLine&{returnl1.x<}Fbin_search(Fs,Fe,T FL=FR=e-while(L<=R Fmid=L+(R-if(!(*mid<val||val<*midreturnelseif(val<*mid)}

R=mid-1;L=mid+return}intMid(CNode*{return(pRoot->L+pRoot->R)}voidInsert(CNode*pRoot,intL,int//在区间 矩形左边的一部分或全部，该左边的一部分或部覆盖了区间{if(pRoot->L==L&&pRoot->R==R){pRoot->Len=y[R+1]-y[L];pRoot->Covers++;}if(R<=Insert(pRoot-elseif(L>=Insert(pRoot-else}

if(pRoot->Covers==0)//如果不为0，则说明本区间当前然被某个矩形完全包含，则不能更新pRoot->Len=pRoot->pLeft->LenpRoot->pRight-}voidDelete(CNode*pRoot,intL,intR)/在区间pRoot删除矩形右边的一部分或全部，该矩形右边的一部分或全部覆if(pRoot->L==L&&pRoot->R==R){pRoot->Covers--;if(pRoot->Covers==0if(pRoot->L==pRoot->RpRoot->Len=return}

pRoot->Len=pRoot->pLeft->LenpRoot->pRight-if(R<=Delete(pRoot-elseif(L>=Delete(pRoot-else}

if(pRoot->Covers0//如果不为0，则说明本区间当前仍然被某个矩形完全包含，则不能更新LenpRoot->Len=pRoot->pLeft->Len+pRoot->pRight-}voidBuildTree(CNode*pRoot,intL,int{pRoot->L=L;pRoot->R=R;pRoot->Covers=0;pRoot->Len=if(L==pRoot->pLeft=Tree+pRoot->pRight=Tree+nNodeCount;BuildTree(pRoot->pLeft,L,(L+R)/2);}int{int int doublex1,y1,x2,y2;intintnCount=0;intt=0;while(true){if(n==0)t yc=lc=for(i=0;i<n;i++)scanf("%lf%lf%lf%lf",&x1,y[yc++]=y1; y[yc++]=y2;lines[lc].x=x1;lines[lc].y1=y1;lines[lc].y2=y2;lines[lc].bLeft=lclines[lc].x=x2;lines[lc].y1=lines[lc].y2=y2;lines[lc].bLeft=false;lc++;}sort(y,y+yc=unique(y,y+yc)-nNodeCount=//yc是横线的条数，yc1是纵向区间的个数，这些区间从 就是yc1BuildTree(Tree,0,yc-1-1);sort(lines,lines+lc);doubleArea=for(i=0;i<lc-1;i++)intL=bin_search(y,y+yc,lines[i].y1)-y;intR=bin_search(y,y+yc,lines[i].y2)-y;if(lines[i].bLeft)Insert(Tree,L,R-Area+=Tree[0].Len*(lines[i+1].x-}}return}

printf("Totalexploredarea:POJ3321ApplePOJ3321Apple有n个节点，就有2n个开始结束时间，它对于序列a，我们设一个数组C[i]=a[i–2k+1]+…+C即为a的树状对于i,如何求2k2k=i&(i^(i-1))i&(-以6为

6-(6)10=(0010)2=通常我们用lowbit(x)表示x对应的2klowbit(x)=x&(-lowbit(x实际上就是x的二进制表示形式C[iC[ia[i-lowbit(i)+1a[i]树状数组的好处在于能快速求任意区间的a[i]+a[i+1]+…+设sum(ka[ia[i+1a[jsum(j)-sum(i-sum(k)=C[n1]+C[n2]+…+ni-1nilowbit(nin1lowbit(n1必须小于或等于0(其实只能等于0）,n1大于0如：sum(6sum(kC[n1]+C[n2C[nm]nm=kni-1=ni-nilowbit(ni)ni的二进制去掉最右边的k的二进制里最多有log2k（向上取整）个1sum(k)=C[n1]+C[n2]+…+ni-1=ni-C[i]=a[i-lowbit(i)+1]+…+ilowbit(i)+1是什么？就是i把最右边的1去sum(kC[n1]+C[n2C[nmnmC[nm]=a[nm-lowbit(nm)+1]+…+a[nm]C[nm-1]=a[nm-1-lowbit(nm-1)+1]+…+a[nm-1]=a[nm-1-lowbit(nm-1)+1]+…+a[nm-lowbit(nm)]C[nm-2]=a[nm-2-lowbit(nm-2)+1]+…+a[nm-2]=a[nm-1-lowbit(nm-1)+1]+…+a[nm-1-lowbit(nm-C[n1]=a[n1-lowbit(n1)+1]+…+=a[1]+…+(n1-lowbit(n1必须等于0，否则就还需C[n1-C[n1],C[n2],其中，n1i，ni+1ni小于等于同理，总的来说更新一个元素的时间，也logNC[n1],C[n2],其中，n1i，ni+1nia[i]更新C[i]C[ia[x而且，C[k+lowbit(k)]的起始 C[k需要更新C[k+lowbit(k)]C[k+lowbit(k)]的起 C[k]=a[k-lowbit(k)+1]+C[k+lowbit(k)]=a[k+lowbit(k)–+k–lowbit(k)>=k+lowbit(k)–易证,lowbit(k+lowbit(k2*C[k+lowbit(k)]的起 下面要证明，若C[i]更新,则对任何k,(C[k]=a[k-lowbit(k)+1]+…+a[k]只要证明k-lowbit(k)+1比i大即因ki)的最右边是从右到左从第那)将变后，再。那么k一定是从到最 都同位(有位全C[k]=sum(k)–sum(k-sum(k)=C[n1]+C[n2]+…+C[nm-1]+C[nm](nm=k)nm-1=k-lowbit(k)sum(k-lowbit(k))=C[n1]+C[n2]+…+C[nm-树状数组时间复杂建数组更新局部求和POJ3321Apple一共有多少个苹(分叉点数100,000Sample3113QCQ

Sample32#include<iostream>#include<vector>usingnamespacestd;#defineMY_MAXinttypedefvector<int>VCT_INT;vector<VCT_INTG(MY_MAX/2//邻接表intLowbit[MY_MAX];boolintStart[MY_MAX//dfs时的开始时间intEnd[MY_MAX];//dfs时的结束时间intnCount=0;voidDfs(int{Start[v]=++for(inti=0;i<G[v].size();i++End[v]=++nCount;}intQuerySum(int{intnSum=0;while(p>0)nSum+=C[p];p-=Lowbit[p];}return}voidModify(intp,int{while(p<=nCount)C[p]+=p+=}}int{intn;intx,y;intfor(i=0;i<n-1;i++){inta,b;G[a].push_back(b//a有边连到b}nCount=for(i=1;i<=nCount;i++)Lowbit[i]=i&(i^(i-}for(i=1;i<=n;i++HasApple[i]=intfor(i=1;i<=nCount;i++)C[i]=i-(i-//C[i]=Sum[i]-Sum[i-for(i=0;i<m;i++)charinta;if(cmd[0]=='C')if(HasApple[a])Modify(Start[a],-1);Modify(End[a],-1);HasApple[a]=0;}else

else}

Modify(Start[a],1);Modify(End[a],1);HasApple[a]=1;intt1=QuerySum(End[a]);intt2=QuerySum(Start[a]-1);printf("%d\n",(t1-t2)/2);}}}二维二维树状C[x][y]=∑x-lowbit[x]+1<=iy-lowbit[y]+1<=jSum[x][yCi][j]}(从[1,1到[x,y]这个a矩i1=x,i2=i1-lowbit(i1),…ik=ik-1-lowbit(ik-1)j1=y,j2=j1-lowbit(j1),…jk=jk-1-lowbit(jk-1)复杂度都是log(n)*log(m)，建C数组复杂度O(m*n)(n,m分别为两维的大小)POJ1195MobileSample01122002111112-21123SampleOutput4#include<iostream>#include<vector>#include<cstring>usingnamespace#defineMY_MAXintintintvoidAdd(inty,intx,int{while(y<=s)inttmpx=while(tmpx<=s)C[y][tmpx]+=tmpx+=}y+=}}intQuerySum(inty,int{intnSum=0;while(y>0)inttmpx=x;while(tmpx>0){nSum+=C[y][tmpx];tmpx-=Lowbit[tmpx];}y-=}return}intmain()int int int intfor(i=1;i<=MY_MAX;i++)Lowbit[i]=i&(i^(i-while(true)switch(cmd)casecasecase

scanf("%d",&memset(C,0,sizeof(C));Add(y+1,x+1,a);scanf("%d%d%d%d",&l,&b,intl++;b++;r++;tQuerySum(b-1,l-1)-QuerySum(t,l-1)-QuerySum(b-case return}}}[x1,y1]–[x2,y2]，那[x1,y1]–[(x1+x2)/2,[x1,(y1+y2)/2+1]–[(x1+x2)/2+1,y1]–[x2,[(x1+x2)/2+1,(y1+y2)/2+1]–二维线段树的四叉树实现形式，请参： 二维线段 intTree[MY_MAX*3][MY_MAX*020215 15[1,3] [4,5]

83456796834567961212y:1–5,x:1-y:6–9,x:1-y:1–3,x:1-y:4–5,x:1-010155

[1,3] [4,5]

926y:6–9,x:4-92683456712]83456712Tree[1][0放着的是该矩形的和y15,x1-9Tree[2][0放着的是该矩形的和y69,x1-9Tree[3][0放着的是该矩形的和y13,x1-9Tree[4][0放着的是该矩形的和y45,x1-9Tree[1][2放着的是该矩形的和y15,x6-001[1,3]1

[4,5]

22565683945 83945 91212001[1,3]1

[4,5]

22565683945 83945 91212Tree[0][4]Tree[2][4]Tree[5][4]Tree[11][0]Tree[11][1]Tree[11][4]#include<iostream>usingnamespacestd;#defineMY_MA