线段树和树状数组-welcometopkujudgeonline

《线段树和树状数组-welcometopkujudgeonline》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线段树和树状数组北京大学信息学院郭炜GWPL@PKU.EDU.CN课程网页http://acm.pku.edu.cn/JudgeOnline/summerschool/pku_acm_train.htm上机地点：理科1号楼1235线段树和树状数组北京大学信息学院郭炜GWPL@PKU.EDU.CN线段树(IntervalTree)实际上还是称为区间树更好理解一些。树：是一棵树，而且是一棵二叉树。线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)同一层的节点所代表的区

2、间，相互不会重叠。叶子节点的区间是单位长度，不能再分了。线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b](除法去尾取整）。•区间[1,9]的线段树和子区间[2,8]的分解[1,9][1,4][5,9][1,2][3,4][5,6][7,9]1234567[8,9]每个区间的长度是区间内整数的个数89叶子节点长度为1

3、，不能再往下分若一个节点对应的区间是[a,b],则其子节点对应的区间分别是[a,(a+b)/2]和[(a+b)/2+1,b]（除法去尾取整）线段树的平分构造，实际上是用了二分的方法。线段树是平衡树，它的深度为log(b-a+1)。2线段树的特征1、线段树的深度不超过logL（L是最长区间的长度）。2、线段树把区间上的任意一条线段都分成不超过2logL条线段。•这些结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据线段树的构建function以节点v为根建树、v对

4、应区间为[l,r]{对节点v初始化if(l!=r){以v的左孩子为根建树、区间为[l,(l+r)/2]以v的右孩子为根建树、区间为[(l+r)/2+1,r]}}线段树的基本用途线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。线段树应用举例给你一个数的序列AA……A。并且可能12n多次进行下列两个操作：1、对序列里面的某个数进行加减2、询问这个序列里面任意一个子序列AA……A的和是多少。

5、ii+1j希望第2个操作每次能在logn时间内完成线段树应用举例显然，[1,n]就是根节点对应的区间可以在每个节点记录该节点对应的区间里面的数的和Sum。对于操作1：因为序列里面A最多只会被线i段树的Logn个节点覆盖。只要求对线段树覆盖A的节点的Sum进行加减操作。i对于操作2：同样只需要找到区间所覆盖的区域，然后把所找区域的Sum累加起来。线段树应用举例如果走到节点[L,R]时，如果要查询的区间就是[L,R](求AL到AR的和）那么直接返回该节点的Sum如果不是，则：对于区间[L,R]，取

6、mid=（L+R）/2；然后看要查询的区间与[L,mid]或[mid+1,R]哪个有交集，就进入哪个区间进行进一步查询。最后通过左右儿子区间的Sum值的维护调整当前区间Sum值。因为这个线段树的深度最深的LogN，所以每次遍历操作都在LogN的内完成。但是常数可能很大。线段树应用举例如果是对区间所对应的一些数据进行修改，过程和查询类似。用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的），以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更

7、新效率最坏就可能变成O(n)的了。先建树，然后插入数据，然后更新，查询。例题：POJ3264BalancedLineup给定Q(1≤Q≤200,000)个数A,A…A,，12Q多次求任一区间A–A中最大数和最小数的ij差。本题树节点结构是什么?例题：POJ3264BalancedLineup给定Q(1≤Q≤200,000)个数A,A…A,，12Q多次求任一区间A–A中最大数和最小数的ij差。本题树节点结构：structCNode{intL,R;//区间起点和终点intnMin,nMax;//本区间里的最大最小

8、值CNode*pLeft,*pRight;};SampleInputSampleOutput63613703425154622POJ3468ASimpleProblemwithIntegers给定Q(1≤Q≤100,000)个数A,A…A,，12Q以及可能多次进行的两个操作:1)对某个区间A…A的个数都加n(n可变）ij2)求某个区间A…A的数的和ij本题树节点要存哪些信息？只存该区间