数据结构选讲 北京大学 陈瑜希

竞赛中会涉及到的基本数据结构 线段树(树状数组) 伸展树 自动机 后缀数组 并查集

线段树的定义

线段树的定义

线段树的构建 function 以节点v为根建树、区间为[l,r] { 对节点v初始化 if (l!=r) 以v的左孩子为根建树、区间为[l,(l+r)/2] 以v的右孩子为根建树、区间为[(l+r)/2+1,r] }

线段树的特征 1、线段树的深度不超过logL。 2、线段树把区间上的任意一条线段都分成不超过2logL条 线段。 这些结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据

线段树的基本操作 给定data[0]…data[n-1] 每个指令为下面两种操作中的一种： 给定k，修改data[k]的值 询问一个区间[l,r]里的data[l]…data[r]的最 小值

线段树的定义

线段树的插入

线段树的插入 把data[5]的值修改为10

线段树的插入 function 修改以节点v为根的子树、区间为[l,r] { 如果修改点不属于[l,r] 跳出 修改节点v的值 if (l!=r) 以v的左孩子为根建树、区间为[l,(l+r)/2] 以v的右孩子为根建树、区间为[(l+r)/2+1,r] }

线段树的查询 查询data[1]…data[7]中的最小值

线段树的查询 function 在节点v查询区间[x,y] { if v所表示的区间与[x,y]的交集为空， 跳出 if v所表示的区间完全属于[x,y] 选取v else 在v的左孩子查询[x,y] 在v的右孩子查询[x,y] }

例题 (ioi 05 moutain ) 有一个轨道，开始高度都为0 给定一系列指令，每个指令为下面两种 操作中的一种： 改变[a,b]的斜率为d 求最大的k，使得[0,k]中任意高度不超过h

数据范围 指令数<100000 轨道长度<1000000000 斜率<1000000000

例题 由于操作数范围巨大，我们希望找到一个算法，使得每 一次插入或者查询的时间复杂度都控制在O(logN)以内 题目中涉及到线段的插入，线段最大值的查询，很容易 联想到线段树 每条线段上需要知道的信息：最高点的高度 由于斜率随时改变，如果直接记录某段最高点的高度， 改变了前面的高度，后面的也需要同时改变，这样会给 维护带来很多麻烦。 所以需要记录一些不太容易改变的量。即修改某条线段 不能影响到其它线段的值。

例题 我们对每条线段记录这些的信息： 1、这段是否被整段覆盖过，如果是，那么 这段的斜率是多少 2、这段的最高点比该段起点高出多少？ (也可以是负的) max 3、这段终点比起点高出多少？height

例题 如何维护？ function updata(p) { p->height=p的左孩子->height+p的右孩子->height p->max=max{p的左孩子->max, p的左孩子->height+p的右孩子->max} }

例题 如何处理巨大的轨道长度？ 方法1、离散化 优点：方法常见，实现简单 缺点：需预先知道所有的长度，是离线算 法 方法2、动态申请空间

动态申请空间 假设长度为10 开始只有一个根节点[0,9] 插入[1,7]后

动态申请空间 方法2、动态申请空间 优点：可以处理无法预先知道所有长度的 题目，是在线算法 缺点：时间与空间复杂度都是O(nlogc) 而 方法一的时间复杂度是O(nlogn) 空间复杂 度为O(n)

例题 (poj3739) 给定n1条平行于x轴的直线，n2条平行 于y轴的直线，n3个点(n1,n2,n3<1001) 且坐标范围<1001 统计包含点的正方形个数，要求正方形 的四条边都在给定的直线上

例题 题目设置了两个障碍： 目标是统计正方形的个数，不是长方形的 个数 要求正方形中有点 很自然的想法：枚举边长

例题 首先枚举边长k 如果知道了正方形的左边界L，也就可以知道 正方形的右边界L+k，那么x坐标在[L,L+k]中的 点在正方形中的x坐标就不影响了，二维问题 转化成了一维问题 现在的问题是：已知一条线段上所有点的位置， 如何快速满足下列条件的线段的个数： 长度为k 包含点 线段端点选自于给定的表中

例题 要考虑长度为k的线段条数并不容易 变通：线段中包含点，也可以转化为把点 延长到长度为k，要求线段的一个端点在 这个区间内 问题转化为： 每个点有一个权值（由最初给定的直线决定） 插入（删除）一些线段，线段覆盖了一些点 求被覆盖的点的权值和

树状数组 原数组是a，c是a的树状数组

可以发现这些规律 C1=a1 C2=a1+a2 C3=a3 C4=a1+a2+a3+a4 C5=a5 …… C8=a1+a2+a3+a4+a5+a6+a7+a8 C2n=a1+a2+….+a2n

树状数组 对于序列a，我们设一个数组C C即为a的树状数组 如何求k？ C[i] = a[i – 2k + 1] + … + a[i] k为i在二进制下末尾0的个数 C即为a的树状数组 如何求k？

以6为例 (6)10=(0110)2 xor 6-1=(5)10=(0101)2 (0011)2 and (6)10=(0110)2 2k=x &(x^(x-1)) 以6为例 (6)10=(0110)2 xor 6-1=(5)10=(0101)2 (0011)2 and (6)10=(0110)2 (0010)2

树状数组 void change(int k,int delta); { while (k<=n) c[k]+=delta,k+=lowbit(k); } int getsum(int k) int t=0; while (k>0) t+=c[k],k-=lowbit(k); return t;

树状数组 树状数组VS线段树 优点：代码简单、空间时间常数小 缺点：有哪些题线段树可以做，树状数 组不能做的？ 树状数组能解决的问题大多为求和问题， 如果已知节点p的值和p的左孩子的值，能 推出p的右孩子的值，大多可以用树状数组 解决

伸展树 伸展树(Splay Tree)是二叉查找树的改进， 比一般二叉查找树再加了伸展操作 伸展操作的目的是使二叉查找树尽可能随 机，避免退化 对伸展树的操作的平摊复杂度是O(log2n)。 伸展树的空间要求、编程难度相对于其它 平衡二叉树来说非常低。

伸展操作Splay(x,S) 伸展操作Splay(x,S)是在保持伸展树有 序性的前提下，通过一系列旋转操作将 伸展树S中的元素x调整至树的根部的操 作。 在旋转的过程中，要分三种情况分别处 理： 1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag 3)Zig-Zag 或 Zag-Zig

伸展操作Splay(x,S) 情况1 Zig或Zag操作： 节点x的父节点y是根节点。

伸展操作Splay(x,S) 情况2 Zig-Zig或Zag-Zag操作： 节点x的父节点y不是根节点，且x与y同时是各 自父节点的左孩子或者同时是各自父节点的右 孩子。

伸展操作Splay(x,S) 情况3 Zig-Zag或Zag-Zig操作： 节点x的父节点y不是根节点，x与y中一个是其父 节点的左孩子而另一个是其父节点的右孩子。

合并操作 Join(S1,S2)：将两个伸展树S1与S2合并。其中 S1的所有元素都小于S2的所有元素。 首先，找到伸展树S1中的最大元素x，再通过 Splay(x,S1)将x调整为S1的根。然后将S2作为x 节点的右子树。这样，就得到了新伸展树S。

分离操作 Split(x,S)：以x为界，将伸展树S分离为两棵伸 展树S1和S2，其中S1中所有元素都小于x，S2 中的所有元素都大于x。 首先执行Find(x,S)，将元素x调整为伸展树的 根节点，则x的左子树就是S1，而右子树为S2。

伸展树 伸展树不仅可以处理点的问题，也可以 处理线段的问题 处理点的问题，往往可以用stl里的set、 map解决

伸展树 处理线段的问题：在每个点记录以这个点 为根的子树的整体信息(如求最小值时， 就是记这个子树中所有点的最小值) 插入、删除、查找、求值等操作的维护， 都与线段树相近 但更加灵活，因为树的结构也是可变的 可以说，伸展操作是伸展树的精髓

例题 给定N个数P1 P2 …PN (N<100001) 第i次操作 对i=1..N依次操作，并对每个i输出相应 的k 选取Pi …PN 中最小的一个数（相同的取位 置靠前的）设为Pk 对Pi …Pk 进行翻转操作，即变为Pk …Pi 对i=1..N依次操作，并对每个i输出相应 的k

例题 线段树？树状数组？ set？map？ 如何处理翻转操作？

例题 由于节点会位置会随时变动，无法找到像 线段树那样编写简单而又节约的方法 需要一个用指针或者用数组模拟指针，可 动态申请空间，并记录下 左孩子右孩子的位置(指针) 节点子树中的相对位置n，这个位置存的数 线段中的最小值min 线段被翻转的次数是奇数还是偶数 由于翻转而产生的位移 如果翻转次数为偶数，则节点的的实际位置为n+k，否则为k-n

例题 找最小值的位置： function findmin() { p=根节点 while (p不为叶子节点) if (p->min==p的左孩子>min) p=p的左孩子 else if (p->min==p的右孩子>min) p=p的右孩子 else 返回p； } 返回p; }

例题 翻转[x,y] 用分离操作把[1,n]分离成：[1,x-1],[x,y], [y+1,n] 改变[x,y]这段根的标记 用合并操作把三段合并起来

伸展树 伸展树VS线段树 缺点：代码麻烦，时间空间常数大 优点：能处理线段树不能处理的问题 （如翻转等）

二维线段树 很容易有这样的问题，在二维中，线段 树还可用吗？

线段树的特征 1、线段树的深度不超过logL。 2、线段树把区间上的任意一条线段都分成不超过2logL条 线段。 这些结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据 而这种树结构不能保证第2条，所以会退化

二维线段树 需要采用树套树，即每个线段树的节点 [l,r]也保存一个线段树，保存横坐标在 [l,r]间的集体情况 所有性质与线段树类似，插入、删除、 查找等时间复杂度为O(log2n)。

例题 问题描述： 在一个长为D、宽为S、无限高的3维空间里， 开始丢N个俄罗斯方块(长方体)。 长方体会一直下落到碰到了已有长方体为止。 给定每个长方体的长、宽、高以及长方体的位 置坐标，问所有长方体下落完之后，整个空间 里最高点的高度。（N<=20000 D，S<=1000）

例题 这个问题实际上是需要处理这么2个操 作： 询问给定区域里的最大高度 把给定区域全部赋值为某个大于当前高度 的已知高度。

例题 不妨先考虑下一维的算法，即需要处理 如下2个操作： 要处理这个问题，线段树的每个节点需 要记录2个值： 询问给定线段里的最大高度 把给定线段全部赋值为某个大于当前高度 的已知高度。 要处理这个问题，线段树的每个节点需 要记录2个值： 当前线段中某个点的最大高度max 整段覆盖当前线段的最大高度cover

例题 处理询问操作 function ask(p) { 若当前区间被询问区间整段覆盖，返回p->max 否则若当前区间与询问区间相交， 则返回max{p->cover,ask(p->left),ask(p->right)} }

例题 处理插入操作 function insert(p,k) { 若当前区间被插入区间整段覆盖，p->cover>?=k;p->max>?=k 否则若当前区间与插入区间相交， p->max>?=k 插入进当前区间的的左孩子和右孩子 } }

例题 缺点： 没有利用到行与行之间的连续性，时间复 杂度O(NSlogD)。会超时

例题 因此，考虑二维线段树： 一维中，我们对于每个区间记录2个信息，那么扩 展到二维，就要记录4个信息： 行被整段覆盖，列也被整段覆盖的最大高度cover,cover 行中的某点，列被整段覆盖的最大高度max,cover 行被整段覆盖，列中的某点最大高度cover,max 区域里的某点的最大高度max,max 在处理询问和插入操作时，需要先递归的分行， 再分列，对与行列分别操作，且操作方法和一维 是基本上相同的 时间复杂度为O(NLogslogd)。空间复杂度为(SD)。

例题 处理询问操作 function asky(sign=(max/cover),p) { 若当前区间被询问区间整段覆盖，返回p->sign,max 否则若当前区间与询问区间相交， 则返回max{p->sign,cover,ask(sign,p->left),ask(sign,p->right)} } function askx(p) 若当前区间被询问区间整段覆盖，asky(max) 则返回max{asky(cover),ask(p->left),ask(p->right)}

例题 处理插入操作 function inserty(sign=(cover/max),p,k) { 若当前区间被插入区间整段覆盖，p->sign,cover>?=k;p->sign,max>?=k 否则若当前区间与插入区间相交， p->sign,max>?=k 插入进当前区间的的左孩子和右孩子 } } function insertx(p,k) 若当前区间被插入区间整段覆盖，inserty(cover,p,k) inserty(max,p,k) inserty(max,p,k)

例题 在n×n矩形里，有两种操作 1、同时给一个矩形内所有数增加一个 相同值 2、询问一个矩形内所有数之和

拓展 三维线段树、四维线段树。。。

例题 (uva 3294) 有一些竹子，给定它们的位置，数量L 以及可口度D 熊猫每次吃竹子都要比以前吃的更可口， 并且与上次吃竹子的位置的曼哈顿距离 不能超过这次竹子的数量 问熊猫最多能吃到多少次竹子

例题 由于要求以竹子的可口度为序，很容易 联想到动态规划。 先按照可口度排序，然后用f(i)表示熊 猫最后一次吃了第i个竹子的情况下， 最多吃了多少次竹子。则 f(i)=max{f(j)}+1 (j<i且|xi-xj|+|yi-yj|<=Li)。 这样做是O(n2)的。显然会超时。

例题 仔细观察这个方程，发现： |xi-xj|+|yi-yj|<=Li这个区域实际上是个正方形 如果我们能利用二维线段树，把每个点的f值插 入到它的坐标上，然后每次只要查询|xi-xj|+|yi- yj|<=Li这个正方形里的最大值，就可以在 O(log2n)的时间内算出每个f了。 不过这个正方形是立着的，为了方便计算，我 们首先把所有坐标都旋转45度，这样这些正方 形就变成了我们经常处理到的躺着的正方体。

例题 假设某个点的坐标为(x,y)，则旋转后它 的坐标为（x+y,y-x），|xi-xj|+|yi-yj|<=Li 这块区域的坐标就是 以(xj+yj-Li,yj-li-xj)为左上角 以(xj+yj+li,yj+li-xj)为右下角的矩形区域。 这样这个问题就成为了标准线段树问题。

例题 如何处理巨大的坐标范围？ 方法1、离散化 方法2、动态申请空间 可把坐标范围106降低到105，但是由于是二维的， 所以空间需要1010，依然行不通 方法2、动态申请空间 由于线段树的深度为O(log2N)，而每进入一层线段 树都会多需要一个节点，而且这些节点有可能被 公用，也可能单独使用，所以最坏的情况下，会 出来O(Nlog2N)个节点 空间复杂度为O(Nlog2N)，遗憾的是，对于 N=100000的情况，还是大了点 之所以会太大，是因为二维线段树的2维分别把一 个节点变成了logN个。如何改变这种浪费呢？

例题 处理这个问题，还可以考虑平衡树。使用平衡树并不会 产生多余的节点，每个点放入平衡树中，还有只有1个点。 如果能把第二维的线段树改为平衡树，空间复杂度可以 降低到O(NlogN)，这样就可以承受了。 平衡树的一维处理需要记录这样的内容： 当前点的f， 以当前点位根的子树中f的最大值 它的纵坐标 左孩子和右孩子。 平衡树以它的纵坐标为序。至于如何插入和查询，应该 是大家很熟悉的了，这里就不再赘述了。 线段树套平衡树时，只需要把一个点插入到线段树上路 径上每个点的平衡树里。

总结 这个问题看似容易，但由于坐标范围巨 大，导致了时间足够但空间不够。从这 里我们发现，单单掌握线段树是不够的， 还需要合理运用各种数据结构，并分析 出它们各自的优势和缺陷，才能做好数 据结构问题。

总结 线段树、树状数组、伸展树都是acm程序 设计竞赛中的基本数据结构，它们的基本 操作希望大家能熟练掌握 数据结构题的难点往往不在于实现，而在 于对问题的具体分析，最重要的是要掌握 各种数据结构能解决什么样的题，这样为 进一步分析提供了方向 当然，题目千变万化，还需具体问题具体 分析，不断产生新的思路，这也是竞赛中 最有趣的地方