PKU线段树

线段树和树状数组 北京大学信息学院 郭炜 GWPL@PKU.EDU.CN 课程网页 http://acm.pku.edu.cn/JudgeOnline/ summerschool/pku_acm_train.htm 上机地点：理科1号楼1235 线段树和树状数组 北京大学信息学院 郭炜 GWPL@PKU.EDU.CN 线段树(Interval Tree)  实际上还是称为区间树更好理解一些。  树：是一棵树，而且是一棵二叉树。  线段：树上的每个节点对应于一个线段(还是叫 “区间”更容易理解，区间的起点和终点通常为 整数)  同一层的节点所代的区间，相互不会重叠。  叶子节点的区间是单位长度，不能再分了。 线段树是一棵二叉树，树中的每一个结 点表示了一个区间[a,b]。a,b通常是整数。 每一个叶子节点表示了一个单位区间。 对于每一个非叶结点所表示的结点[a,b]， 其左儿子表示的区间为[a,(a+b)/2]，右儿 子表示的区间为[(a+b)/2,b](除法去尾取 整）。 • 区间[1, 9]的线段树和子区间[2, 8]的分解 每个区间的长度是区间内整数的个数 叶子节点长度为1，不能再往下分 若一个节点对应的区间是[a,b],则其子节点对应的区间分别是 [a,(a+b)/2]和[ (a+b)/2+1,b] （除法去尾取整） 线段树的平分构造，实际上是用了二分的。线段树是平衡树，它 的深度为log2(b-a+1)。 [1,9] [1,4] [5,9] [1,2] [3,4] [5,6] [7,9] [8,9]1 2 3 4 5 6 7 8 9 线段树的特征  2、线段树把区间上的任意一条线段都分成不超过 2logL条线段。 • 这些结论为线段树能在O(logL)的时间内完成一条线段的 插入、删除、查找等工作，提供了理论依据  1、线段树的深度不超过logL（L是最长区间的长度）。 线段树的构建  function 以节点v为根建树、v对应区间为[l,r]  {  对节点v初始化  if (l!=r)  {  以v的左孩子为根建树、区间为[l,(l+r)/2]  以v的右孩子为根建树、区间为[(l+r)/2+1,r]  }  } 线段树的基本用途  线段树适用于和区间统计有关的问题。比如某些数据 可以按区间进行划分，按区间动态进行修改，而且还 需要按区间多次进行查询，那么使用线段树可以达到 较快查询速度。 线段树应用举例 给你一个数的序列A1A2……An。 并且可能 多次进行下列两个操作：  1、对序列里面的某个数进行加减  2、询问这个序列里面任意一个子序列 AiAi+1……Aj的和是多少。 希望第2个操作每次能在logn时间内完成 线段树应用举例 显然，[1,n]就是根节点对应的区间 可以在每个节点记录该节点对应的区间里 面的数的和Sum。 对于操作1：因为序列里面Ai最多只会被线 段树的Logn个节点覆盖。只要求对线段树 覆盖Ai的节点的Sum进行加减操作。 对于操作2：同样只需要找到区间所覆盖的 区域，然后把所找区域的Sum累加起来。 线段树应用举例  如果走到节点[L,R]时，如果要查询的区间就是[L,R]  (求AL到AR的和）那么直接返回该节点的Sum  如果不是，则：  对于区间[L,R]，取mid=（L+R）/2；  然后看要查询的区间与[L,mid]或[mid+1,R]哪个有交 集，就进入哪个区间进行进一步查询。  最后通过左右儿子区间的Sum值的维护调整当前区 间Sum值。  因为这个线段树的深度最深的LogN，所以每次遍历 操作都在LogN的内完成。但是常数可能很大。 线段树应用举例  如果是对区间所对应的一些数据进行修改，过程和查询 类似。  用线段树解题，关键是要想清楚每个节点要存哪些信息 （当然区间起终点，以及左右子节点指针是必须的）， 以及这些信息如何高效更新，维护，查询。不要一更新 就更新到叶子节点，那样更新效率最坏就可能变成O(n) 的了。  先建树，然后插入数据，然后更新，查询。 例题： POJ 3264 Balanced Lineup 给定Q (1 ≤ Q ≤ 200,000)个数A1,A2 … AQ,， 多次求任一区间Ai – Aj中最大数和最小数的 差。 本题树节点结构是什么? 例题： POJ 3264 Balanced Lineup 给定Q (1 ≤ Q ≤ 200,000)个数A1,A2 … AQ,， 多次求任一区间Ai – Aj中最大数和最小数的 差。 本题树节点结构： struct CNode { int L,R; //区间起点和终点 int nMin,nMax;//本区间里的最大最小值 CNode * pLeft, * pRight; }; Sample Input 6 3 1 7 3 4 2 5 1 5 4 6 2 2 Sample Output 6 3 0 POJ 3468 A Simple Problem with Integers 给定Q (1 ≤ Q ≤ 100,000)个数A1,A2 … AQ,， 以及可能多次进行的两个操作: 1) 对某个区间Ai … Aj的个数都加n(n可变） 2) 求某个区间Ai … Aj的数的和 本题树节点要存哪些信息？只存该区间的 数的和，行不行？ POJ 3468 A Simple Problem with Integers 只存和，会导致每次加数的时候都要更新 到叶子节点，速度太慢，这是必须要避免 的。 本题树节点结构： struct CNode { int L ,R; //区间起点和终点 CNode * pLeft, * pRight; long long nSum; //原来的和 long long Inc; //增量c的累加 }; //本节点区间的和实际上是nSum+Inc*(R-L+1) POJ 3468 A Simple Problem with Integers 在增加时，如果要加的区间正好覆盖一个 节点，则增加其节点的Inc值，不再往下走 ，否则要更新nSum,再将增量往下传 在查询时，如果待查区间不是正好覆盖一 个节点，就将节点的Inc往下带，然后将Inc 代表的所有增量累加到nSum上后将Inc清0 ，接下来再往下查询。 离散化 有时，区间的端点不是整数，或者区间太 大导致建树内存开销过大MLE ,那么就需要 进行“离散化”后再建树。 POJ 2528 Mayor's posters 给定一些海报，可能互相重叠，告诉你每 个海报宽度（高度都一样）和先后叠放次 序，问没有被完全盖住的海报有多少张。 海报最多10,000张，但是墙有10,000,000 块瓷砖长。海报端点不会落在瓷砖中间。 POJ 2528 Mayor's posters 如果每个叶子节点都代表一块瓷砖，那么线段 树会导致MLE，即单位区间的数目太多。 实际上，由于最多10,000个海报，共计20,000 个端点，这些端点把墙最多分成19,999个区间 （题意为整个墙都会被盖到） 我们只要对这19,999个区间编号，然后建树即 可。这就是离散化。 POJ 2528 Mayor's posters 如果海报端点坐标是浮点数，其实也一样处理。 树节点要保存哪些信息，而且这些信息该如何 动态更新呢？ POJ 2528 Mayor's posters struct CNode { int L,R; bool bCovered; CNode * pLeft, * pRight; }; bCovered表示本区间是否已经完全被海报 盖住 关键： 插入数据的顺序 ------ 从底至上依次 插入每张海报 POJ 1151 Atlantis 给定一些矩形，其顶点坐标是浮点数，可 能互相重叠，问这些矩形覆盖到的面积是 多大。 用线段树做，先要离散化！！ POJ 1151 Atlantis 在Y轴进行离散化。n个矩形的2n个横边纵 坐标共构成最多2n-1个区间的边界，对这 些区间编号，建立起线段树。 POJ 1151 Atlantis 线段树的节点要保存哪些信息？如何将一 个个矩形插入线段树？插入过程中这些信 息如何更新？怎样查询？ POJ 1151 Atlantis struct CNode { int L,R; CNode * pLeft, * pRight; double Len; //落在本区间的线段总长度 int Covers;//本区间被完全覆盖的重数 }; 上面的“线段”指的是真实的线段，即由矩 形的边构成的，不是“区间”的意思 POJ 1151 Atlantis 插入数据的顺序： 将矩形的纵边从左到右排序，然后依次将这 些纵边插入线段树。要记住哪些纵边是一个 矩形的左边(开始边)，哪些纵边是一个矩形 的右边（结束边），以便插入时，对Len和 Covers做不同的修改。 插入一条边后就更新总覆盖面积的值。 有时，不一定能够一眼看出什么是“区间”， 这就要靠仔细观察，造出“区间”来。例如： POJ 3321 Apple Tree 每个分叉点及末梢可能有苹果（最多1个）， 每次可以摘掉一个苹果，或有一个苹果新长 出来，随时查询某个分叉点往上的子树里， 一共有多少个苹果。 POJ 3321 Apple Tree 深度优先遍历整个苹果树，为每个节点标记 一个开始时间和结束时间（所有时间都不相 同），显然子树里面所有节点的开始和结束 时间，都位于子树树根的开始和结束时间之 间。 问题变成： 有n个节点，就有2n个开始结束时间，它们构 成序列 A1A2….A2n 序列里每个数是0或者1，可变化，随时查询 某个区间里数的和。当然由于苹果树上每个 放苹果的位置对应于数列里的两个数，所以 结果要除以2 树状数组 对于序列a，我们设一个数组C ◦ C[i] = a[i – 2k + 1] + … + a[i] ◦ k为i在二进制下末尾0的个数 ◦ i从1开始算！  C即为a的树状数组 对于i,如何求2k ？  2k=i &(i^(i-1)) 也就是 i&(-i) 以6为例  (6)10=(0110)2  xor 6-1=(5)10=(0101)2  (0011)2  and (6)10= (0110)2  (0010)2 = (4)10 通常我们用lowbit(x)表示x对应的2k ,  lowbit(x) = x&(-x)  lowbit(x) 实际上就是x的二进制表示形式 留下最右边的1，其他位都变成0 C[i] = a[i-lowbit(i)+1] + …+ a[i] C包含哪些项看上去没有规律  C1=A1  C2=A1+A2  C3=A3  C4=A1+A2+A3+A4  C5=A5  C6=A5+A6  C7=A7  C8=A1+A2+A3+A4+A5+A6+A7+A8  …………  C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+ A11+A12+A13+A14+A15+A16 树状数组图示 树状数组的好处在于能快速求任意区间的和 a[i] + a[i+1] + … + a[j] 设sum(k) = a[1]+a[2]+…+a[k] 则 a[i] + a[i+1] + … + a[j] = sum(j)-sum(j-1) 有了树状数组，sum(k)就能在O(logN)时间内求出， N是a数组元素个数。而且更新一个a的元素所花的 时间也是O(logN)的(a更新了C也得更新)。 为什么呢？ 根据C的构成规律，可以发现sum(k)可以表示为： sum(k) = C[n1]+C[n2] + …+ C[nm] 其中 nm= k ni-1 = ni - lowbit(ni) 而且 n1 – lowbit(n1 ) 必须小于或 等于0 如：sum(6) = C[4]+C[6] lowbit(x) 实际上就是x的二进制表示形式留下最右 边的1，其他位都变成0 那么，sum(k)最多有几项呢？这个决定了求区间和 的时间复杂度 那么，sum(k)最多有几项呢？ sum(k) = C[n1]+C[n2] + …+ C[nm] 其中 nm= k ni-1 = ni - lowbit(ni) lowbit(x) 实际上就是x的二进制表示形式留下最右 边的1，其他位都变成0 ni - lowbit(ni) 是什么样子？就是 ni的二进制去掉最 右边的1 k 的二进制里最多有几个1？ log2 k个 sum(k)最多log2 k项，所以本次求和的复杂度就是 log2 k 那么，为什么 sum(k) = C[n1]+C[n2] + …+ C[nm] 其中 nm= k ni-1 = ni - lowbit(ni) 把每一项C[ni]拆开细算，把ni表示成2的整数次幂的 和就能发现。证明略。 C[i] = a[i-lowbit(i)+1] + …+ a[i] i - lowbit(i)+1 是什么？就是i把最右边的1去 掉，然后再加1  C1=A1  C2=A1+A2  C3=A3  C4=A1+A2+A3+A4  C5=A5  C6=A5+A6  C7=A7  C8=A1+A2+A3+A4+A5+A6+A7+A8  …………  C16=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10+ A11+A12+A13+A14+A15+A16 更新一个a元素，C也要跟着更新，复杂度是多少呢？ 即C里有几项要更新呢？ 如果a[i]更新了，那么以下的几项都需要更新： C[n1], C[n2], …C[nm] 其中，n1 = i ，ni+1 = ni + lowbit(ni) nm + lowbit(nm) 必须大于 a 的元素个数 N 同理，总的来说更新一个元素的时间，也是 logN的 更新一个a元素，C也要跟着更新，复杂度是多少呢？ 即C里有几项要更新呢？ 初始状态下由a构建树状数组C的时间复杂度 是多少？ 显然是 O(N)的 因为 C[k] = sum(k) – sum(k-lowbit(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-1] 所以，树状数组适合单个元素经常修改而且 还反复要求部分的区间的和的情况。 上述问题虽然也可以用线段树解决，但是用 树状数组来做，编程效率和程序运行效率 都更高 如果每次要修改的不是单个元素，而是一个 区间，那就不能用树状数组了(效率过低）。 POJ 3321 Apple Tree 每个分叉点及末梢可能有苹果（最多1个）， 每次可以摘掉一个苹果，或有一个苹果新长 出来，随时查询某个分叉点往上的子树里， 一共有多少个苹果。 此题可用树状数组来做 Sample Input 3 1 2 1 3 3 Q 1 C 2 Q 1 Sample Output 3 2 根据题意，一开始时，所有能长苹果的地 方都有苹果 二维树状数组 原始数组和树状数组都是二维的  C[x][y] = Sum(a[i][j])  x-lowbit[x]+1 <= i <=x  y-lowbit[y]+1 <= j <=y 用于快速求数字子矩阵的和 POJ 1195 Mobile phones 一个由数字构成的大矩阵，能进行两种操作 1) 对矩阵里的某个数加上一个整数（可正可负） 2) 查询某个子矩阵里所有数字的和 要求对每次查询，输出结果 Sample Input 0 4 1 1 2 3 2 0 0 2 2 1 1 1 2 1 1 2 -1 2 1 1 2 3 3 Sample Output 3 4 POJ题目推荐： 2182, 2352, 1177, 3667,3067