C语言-线段树

线段树1线段树2线段树(IntervalTree)实际上还是称为区间树更好理解一些。树：是一棵树，而且是一棵二叉树。线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)。同一层的节点所代表的区间，相互不会重叠。同一层节点所代表的区间，加起来是个连续的区间。叶子节点的区间是单位长度，不能再分了。线段树3线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间(长度为1)。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b](除法去尾取整）。线段树4区间[1,9]的线段树线段树5性质1.每个区间的长度是区间内整数的个数。叶子节点长度为1，不能再往下分。2.若一个节点对应的区间是[a,b]，则其子节点对应的区间分别是[a,(a+b)/2]和[(a+b)/2+1,b]（除法去尾取整）。3.线段树的平分构造，实际上是用了二分的方法。若根节点对应的区间是[a,b]，那么它的深度为log2(b-a+1)+1(向上取整）。线段树64.叶子节点的数目和根节点表示区间的长度相同。5.线段树节点要么0度，要么2度，因此若叶子节点数目为N，则线段树总结点数目为2N-1。6.任两个结点要么是包含关系要么没有公共部分，不可能部分重叠。7.给定一个叶子p，从根到p路径上所有结点(即p的所有直系祖先)代表的区间都包含点p，且其他结点代表的区间都不包含点p。线段树7区间[1,9]的线段树上，区间[2,8]的分解分解的规则就是：如果有某个节点代表的区间，完全属于待分解区间，则该节点为“终止”节点，不再继续往下分解。所有“终止”节点所代表的区间都不重叠，且加在一起就恰好等于整个待分解区间。区间分解的时候，每层最多2个“终止节点”，所以终止节点总数也是log(n)量级的。线段树8和应用相关的几个小问题线段长度为偶数:左小右大还是左大右小？一样大原始线段长度不是2的幂:允许不平均分割还是补齐到2的幂?允许不平均分割叶子是单个元素i还是单位线段[i,i+1]?是单个元素静态or动态?静态建立:自顶向下递归分割还是自底向上合并?分割合并都可以线段树的特征91、线段树的深度不超过log2(n)+1（向上取整，n是根节点对应区间的长度）。2、线段树上，任意一个区间被分解后得到的“终止节点”数目都是log(n)量级。线段树上更新叶子节点和进行区间分解时间复杂度都是O(log(n))的。这些结论为线段树能在O(log(n))的时间内完成插入数据，更新数据、查找、统计等工作，提供了理论依据.线段树的构建10function以节点v为根建树、v对应区间为[l,r]{对节点v初始化if(l!=r){以v的左孩子为根建树、区间为[l,(l+r)/2]以v的右孩子为根建树、区间为[(l+r)/2+1,r]}}建树的时间复杂度是O(n)，n为根节点对应的区间长度。线段树的基本用途11线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。12给你一个数的序列A1A2……An。并且可能多次进行下列两个操作：1、对序列里面的某个数进行加减。2、询问这个序列里面任意一个连续的子序列AiAi+1……Aj的和是多少。希望第2个操作每次能在log(n)时间内完成。线段树应用举例13显然，[1,n]就是根节点对应的区间。可以在每个节点记录该节点对应的区间里面的数的和Sum。对于操作1：因为序列里面Ai最多只会被线段树的log(n)个节点覆盖。只要求对线段树覆盖Ai的节点的Sum进行加操作，因此复杂度是log(n)对于操作2：同样只需要找到区间所覆盖的“终止”节点，然后把所找“终止”节点的Sum累加起来。因为这些节点的数量是O(log(n))的，所以这一步的复杂度也是log(n)。线段树应用举例14如果走到节点[L,R]时，如果要查询的区间就是[L,R](求AL到AR的和）那么直接返回该节点的Sum，并累加到总的和上;如果不是，则：对于区间[L,R]，取mid=(L+R)/2；然后看要查询的区间与[L,mid]或[mid+1,R]哪个有交集，就进入哪个区间进行进一步查询。因为这个线段树的深度最深的logN，所以每次遍历操作都在logN的内完成。但是常数可能很大。线段树应用举例15如果是对区间所对应的一些数据进行修改，过程和查询类似。用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的），以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更新效率最坏就可能变成O(n)的了。先建树，然后插入数据，然后更新，查询。线段树应用举例16例题：POJ3264BalancedLineup给定Q(1≤Q≤200,000)个数A1，A2…AQ，多次求任一区间[Ai,Aj]中最大数和最小数的差。本题树节点结构是什么?本题树节点结构：structCNode{intL,R;//区间起点和终点intminV,maxV;//本区间里的最大最小值CNode*pLeft,*pRight;};线段树应用举例17也可以不要左右节点指针，用一个数组存放线段树。根节点下标为0。假设线段树上某节点下标为i，则:左子节点下标为i*2+1，右子节点下标为i*2+2如果用一维数组存放线段树，且根节点区间[1,n]使用左右节点指针，则数组需要有2n-1个元素。不使用左右节点指针，则数组需要有:2*2[log2n]-1个元素([log2n]向上取整)2*2[log2n]-1=4n-1，实际运用时常可以更小，可尝试3线段树应用举例18SampleInputSampleOutput63//6个数，3次查询613703425154622线段树应用举例19#includeiostreamusingnamespacestd;constintINF=0xffffff0;intminV=INF;intmaxV=-INF;structNode//不要左右子节点指针的做法{intL,R;intminV,maxV;intMid(){return(L+R)/2;}};Nodetree[800010];//4倍叶子节点的数量就够线段树应用举例20voidBuildTree(introot,intL,intR){tree[root].L=L;tree[root].R=R;tree[root].minV=INF;tree[root].maxV=-INF;if(L!=R){BuildTree(2*root+1,L,(L+R)/2);BuildTree(2*root+2,(L+R)/2+1,R);}}线段树应用举例21voidInsert(introot,inti,intv)//将第i个数，其值为v，插入线段树{if(tree[root].L==tree[root].R){//成立则亦有tree[root].R==itree[root].minV=tree[root].maxV=v;return;}tree[root].minV=min(tree[root].minV,v);tree[root].maxV=max(tree[root].maxV,v);if(i=tree[root].Mid())Insert(2*root+1,i,v);elseInsert(2*root+2,i,v);}线段树应用举例22voidQuery(introot,ints,inte)//查询区间[s,e]中的最小值和最大值，如果更优就记在全局变量里{if(tree[root].minV=minV&&tree[root].maxV=maxV)return;if(tree[root].L==s&&tree[root].R==e){minV=min(minV,tree[root].minV);maxV=max(maxV,tree[root].maxV);return;}if(e=tree[root].Mid())Query(2*root+1,s,e);elseif(stree[root].Mid())Query(2*root+2,s,e);else{Query(2*root+1,s,tree[root].Mid());Query(2*root+2,tree[root].Mid()+1,e);}}线段树应用举例23intmain(){intn,q,h;inti,j,k;scanf(%d%d,&n,&q);BuildTree(0,1,n);for(i=1;i=n;i++){scanf(%d,&h);Insert(0,i,h);}for(i=0;iq;i++){ints,e;scanf(%d%d,&s,&e);minV=INF;maxV=-INF;Query(0,s,e);printf(%d\n,maxV-minV);}return0;}线段树应用举例24POJ3468ASimpleProblemwithIntegers给定Q(1≤Q≤100,000)个数A1，A2…AQ，以及可能多次进行的两个操作:1)对某个区间Ai…Aj的每个数都加n(n可变）2)求某个区间Ai…Aj的数的和本题树节点要存哪些信息？只存该区间的数的和，行不行？线段树应用举例25只存和，会导致每次加数的时候都要更新到叶子节点，速度太慢(O(nlogn))，这是必须要避免的。本题树节点结构：structCNode{intL,R;CNode*pLeft,*pRight;longlongnSum;//原来的和longlongInc;//增量c的累加};//本节点区间的和实际上是nSum+Inc*(R-L+1)线段树应用举例26在增加时，如果要加的区间正好覆盖一个节点，则增加其节点的Inc值，不再往下走，否则要更新nSum(加上本次增量),再将增量往下传。这样更新的复杂度就是O(log(n))。在查询时，如果待查区间不是正好覆盖一个节点，就将节点的Inc往下带，然后将Inc代表的所有增量累加到nSum上后将Inc清0，接下来再往下查询。Inc往下带的过程也是区间分解的过程，复杂度也是O(log(n))。线段树应用举例27线段树应用举例28线段树应用举例29线段树应用举例30#includeiostreamusingnamespacestd;structCNode{intL,R;CNode*pLeft,*pRight;longlongnSum;//原来的和longlongInc;//增量c的累加};CNodeTree[200010];//2倍叶子节点数目就够intnCount=0;intMid(CNode*pRoot){return(pRoot-L+pRoot-R)/2;}线段树应用举例31voidBuildTree(CNode*pRoot,intL,intR){pRoot-L=L;pRoot-R=R;pRoot-nSum=0;pRoot-Inc=0;if(L==R)return;nCount++;pRoot-pLeft=Tree+nCount;nCount++;pRoot-pRight=Tree+nCount;BuildTree(pRoot-pLeft,L,(L+R)/2);BuildTree(pRoot-pRight,(L+R)/2+1,R);}线段树应用举例32voidInsert(CNode*pRoot,inti,intv){if(pRoot-L==i&&pRoot-R==i){pRoot-nSum=v;return;}pRoot-nSum+=v;if(i=Mid(pRoot))Insert(pRoot-pLeft,i,v);elseInsert(pRoot-pRight,i,v);}线段树应用举例33voidAdd(CNode*pRoot,inta,int