线段树

线段树问题1：有一列长度为n的数，刚开始全是0。现在执行m次操作，每次可以执行以下两种操作之一：(1)将数列中的某个数加上某个数值；(2)询问给定区间中所有数的和。朴素的模拟：修改O(1)、查询O(n)、总复杂度O(n*m)。低效的原因：维护是针对元素的，但查询是针对区间的。线段树的结构[1,10)[1,5)[5,10)[3,5)[1,3)[7,10)[5,7)[2,3)[1,2)[4,5)[3,4)[6,7)[5,6)[8,10)[7,8)[9,10)[8,9)线段树的结构区间：[a,b)结点T[a,b)维护原数列中区间[a,b)的信息若b-a1，T[a,b)是分支结点，其左右孩子分别为：T[a,(a+b)/2)、T[(a+b)/2,b)。若b-a=1，T[a,b)是叶结点，单位区间。线段树的性质结点数：数列长度为n，总结点个数不超过2*n。深度：近似满二叉树，深度不超过log2(n-1)+1。线段树把区间上的任意一条长度为L的线段都分成了不超过2*log2L条线段，查询在O(log2n)的时间内解决。空间复杂度：O(n)。线段树的存储1.链表存储structlinkst{intLeft,Right;//区间[Left,right)linkst*lptr,*rptr;//左右孩子指针};线段树的存储2.数组模拟链表存储structarrst{//数组模拟链表intLeft,Right;//区间[Left,right)intlptr,rptr;//左右孩子指针};线段树的存储3.堆结构存储线段树去除了最底层之后是一棵满二叉树，因此可以用类似堆的存储方式。根结点存储在1号位置，对于存储在i号位置的结点而言，其左孩子存储在2*i号位置，右孩子存储在2*i+1号位置。最后一层可能很空，造成空间的浪费。线段树的存储4.更紧凑的存储方式对于结点区间为[Left,Right]的结点，存储在(Left+Right)|(Left!=Right)号位置，把每个结点不重复且不遗漏地映射到[2,2n]中。如果结点区间为[Left,Right)左闭右开区间形式，存储在Left+Right-1位置，如果[Left,Right)不是单位区间且(Left+Right)是奇数，存储在Left+Right-2位置。线段树的结构[1,10)[1,5)[5,10)[3,5)[1,3)[7,10)[5,7)[2,3)[1,2)[4,5)[3,4)[6,7)[5,6)[8,10)[7,8)[9,10)[8,9)105324768101214171618161114线段树的结构[1,10)[1,5)[5,10)[3,5)[1,3)[7,10)[5,7)[2,3)[1,2)[4,5)[3,4)[6,7)[5,6)[8,10)[7,8)[9,10)[8,9)105324768101214171618161114线段树的结构[1,10)[1,5)[5,10)[3,5)[1,3)[7,10)[5,7)[2,3)[1,2)[4,5)[3,4)[6,7)[5,6)[8,10)[7,8)[9,10)[8,9)10-9532476810121417161816-151114-13线段树的构造需要维护额外的信息来达到解决问题的目的。问题1中，每个结点需维护对应区间的和。structnode{intLeft,Right;//区间[Left,Right)intlptr,rptr;//左右孩子指针intsum;//区间和}t[2*maxn];建树//递归建立线段树，下标由1开始voidbuildtree(intll,intrr){intcur=++tot;t[cur].Left=ll;t[cur].Right=rr;if(ll!=rr-1){t[cur].lptr=tot+1;buildtree(ll,(ll+rr)/2);t[cur].rptr=tot+1;buildtree((ll+rr)/2,rr);t[cur].sum=t[t[cur].lptr].sum+t[t[cur].rptr].sum;}elset[cur].sum=a[ll];}查询区间和intquery(intk,intll,intrr){//查询[ll,rr)的区间和if(ll=t[k].Left&&rr=t[k].Right)returnt[k].sum;intans=0;if(ll(t[k].Left+t[k].Right)/2)ans+=query(t[k].lptr,ll,rr);if(rr(t[k].Left+t[k].Right)/2)ans+=query(t[k].rptr,ll,rr);returnans;}线段树的修改voidchange1(intk,intp,intdelta){//修改单个元素的值if(t[k].Left==t[k].Right-1)t[k].sum+=delta;else{if(p(t[k].Left+t[k].Right)/2)change1(t[k].lptr,p,delta);if(p=(t[k].Left+t[k].Right)/2)change1(t[k].rptr,p,delta);t[k].sum=t[t[k].lptr].sum+t[t[k].rptr].sum;}}问题2.有一列长度为n的数，刚开始全是0。现在执行m次操作，每次可以执行以下两种操作之一：(1)将数列中某个区间的所有数加上某个数值；(2)询问给定区间中所有数的和。若直接用前面的方法维护修改操作的话，对单个元素的修改操作是O(log2n)，那么区间修改是O(n*log2n)，比直接模拟还慢。线段树的延迟修改在递归修改时，如果发现修改的区间已经覆盖了当前结点，就停止递归，给当前结点作上标记。在以后的维护或查询过程中，需要对这样的结点的标记进行分解，传递给它的子结点。复杂度O(log2n)。voidchange2(intk,intll,intrr,intdelta){if(ll=t[k].Left&&rr=t[k].Right){t[k].sum+=delta*(t[k].Right-t[k].Left);//更新sumt[k].bj+=delta;//累计修改}else{if(t[k].bj)update(k);//传递修改if(ll(t[k].Left+t[k].Right)/2)change2(t[k].lptr,ll,rr,delta);if(rr(t[k].Left+t[k].Right)/2)change2(t[k].rptr,ll,rr,delta);t[k].sum=t[t[k].lptr].sum+t[t[k].rptr].sum;}}voidupdate(intk){//延迟信息下传t[t[k].lptr].sum+=t[k].bj*(t[t[k].lptr].Right-t[t[k].lptr].Left);t[t[k].rptr].sum+=t[k].bj*(t[t[k].rptr].Right-t[t[k].rptr].Left);t[t[k].lptr].bj+=t[k].bj;t[t[k].rptr].bj+=t[k].bj;t[k].bj=0;}intquery2(intk,intll,intrr){if(ll=t[k].Left&&rr=t[k].Right)returnt[k].sum;if(t[k].bj)update(k);intans=0;if(ll(t[k].Left+t[k].Right)/2)ans+=query2(t[k].lptr,ll,rr);if(rr(t[k].Left+t[k].Right)/2)ans+=query2(t[k].rptr,ll,rr);returnans;}矩形覆盖问题Input：第一行：一个整数n(1=n=10000)；以下n行：每行4个整数x1,y1,x2,y2(0=x1x2=30000,0=y1y2=30000)。(x1,y1)和(x2,y2)表示矩形的左下角和右上角坐标Output:一个整数，表示所有矩形的公共面积。InputSample:210102020OutputSample:225一般的模拟算法的时间复杂度可以达到O(n^3)，不理想。用线段树来解决：预处理，坐标离散化；在x轴上维护一棵线段树，区间覆盖模型：把所有矩形的上下边界按y升序排把矩形的上下两边界看作对x轴的覆盖下边界对应对x轴的覆盖；上边界对应对x轴的删除覆盖。对于每个y，统计线段树中已经被覆盖的总长度T.sum，本次扫描出来的面积=t.sum*(cur.y-pre.y)对于y坐标相同的边界，全部处理完毕后，再计算面积的增量。栅栏FarmerJohn为奶牛们设置了一个障碍赛。障碍赛中有n个(n=50000)种各种长度的栅栏，每个都与x轴平行，其中第i个栅栏的y坐标为i。终点在坐标原点(0,0)，起点在(s,n)。奶牛们很笨拙，它们都是绕过栅栏而不是跳过去的。也就是说它们会沿着栅栏走直到栅栏头，然后向着x轴奔跑，直到碰到下一个栅栏挡住去路，然后再绕过去……如果按照这种方法，奶牛从起点到终点需要走的最短距离是多少？(平行于y轴的距离不用计算了，因为这个数是n)输入格式：第一行是两个整数n和s，其中s的绝对值不超过100000。接下来的n行，每行两个整数ai和bi，代表第i个栅栏的两个端点的横坐标。其中100000=aibi=100000,an=s=bn。输出格式：输出仅一个整数，代表x轴方向所需要走的最短距离。样例输入：输出：404-21-12-30-21动规：f(i,0),f(i,1)表示到第i条栅栏左右端点的最小距离，f(i,0)=min{f(j,0)+|ai-aj|,f(j,1)+|bj-ai|}ij=n且栅栏j能直接到栅栏i。时间复杂度O(n2)。栅栏j能否直接到栅栏i需按左右端点分情况处理。换个思路，其实我们只关心能直接到当前端点的那个端点的最小距离，至于它是左端点还是右端点无所谓。如栅栏j的某个端点(xj,j)能直接到栅栏i的某个端点(xi,i)，考虑f(j)+|xi-xj|=f(j)-xj+xi(xjxi)=f(j)+xj-xi(xixj)对于端点(xj,j)，不能只维护f(j)，而是维护f(j)-xj和f(j)+xj两个值，用来参与(xi,i)的计算。数据结构的规划：设到端点(xj,j)的最小距离为k，维护(k-xj)、(k+xj)。求到端点(xi,i)的最小距离，对于xjxi，取min{k-xj+xi}对于xjxi，取min{k+xj-xi}到端点(xi,i)的最小距离等于上述两者再取min，记为k’维护(k’-xi)、(k’+xi)。区间查询和单点修改，可以利用线段树。最后一点，栅栏i[ai,bi]添加后，被栅栏i包含的端点就不能直接更新i之后的栅栏了，区间(ai,bi)的值修改为无穷大。将线段树扩展到高维：二维及更高维的局部和、最值维护问题。1.对划分方案进行调整：一维：一分为二；二维：一分为四；(左上、右上、左下、右下)三维：一分为八退化现象严重：例如查询矩形(二维)的某一整行，四分树将查询到每个1*1的矩形，再返回，复杂度O(n)。将线段树扩展到高维：二维及更高维的局部和、最值维护问题。1.树套树，基于树的嵌套以二维线段树为例：维护两类线段树T1维护x方向T1(a,b)不是一维的区间[a,b)而是x坐标在[a,b)范围内的所有格子，T1(a,b)同时维护一个第二类线段树T2。(x1,y1)(x2,y2)t1(x1,x2+1)-t2(y1,y2+1)复杂度分析：一共有O(n)个第一类线段树结点，每个结点又有一个大小为O(n)的第二类线段树，总的空间复杂度O(n^2)。单词查询的时间复杂度O((logn)^2)。例：3D方块“俄罗斯方块”游戏的作者想做一个新的三维版本。在这个版本中长方块会掉到一个矩形的平台上。这些块按照一定顺序分开落下，就