RMQ问题研究

信息学奥赛⼀本通（提⾼组）⼀、贪⼼算法选择不相交区间问题：给定n个开区间，选择尽量多个区间，是得这些区间两两没有公共点。

（例：活动安排） 按照结束时间由⼩到⼤的顺序排列，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

区间选点问题：给定n个闭区间，在数轴上选尽量少的点，是得每个区间内都⾄少有⼀个点（不同区间内含的点可以是同⼀个）。

（例：种树） ⾸先按照区间的结束位置从⼩到⼤排列。

然后在区间中进⾏选择：对于当前区间，若集合中的点不能覆盖它，则将区间末尾的数加⼊集合。

贪⼼策略：取最后⼀个。

区间覆盖问题：给定n隔壁区间，选择尽量少的区间覆盖⼀条指定的线段区间。

（例：喷⽔装置） 将所有区间按照左端点由⼩到⼤排序，依次处理每个区间。

每次选择覆盖点s的区间中右端点坐标中最⼤的⼀个，并将s更新为该区间的右端点坐标，直到选择的区间包含t。

贪⼼策略：在某时刻的s，找出⼀个满⾜a[i]<=s的b[i]最⼤值即可。

流⽔作业调度问题：n作业，两机器，先a后b，求总时间最短。

（例：加⼯⽣产调度） 直观：让a没有空闲，让b空的少 Johnson算法：对于a<b的集合，按s⾮减序排列；对于a>=b的集合，按照b⾮升序排列带期限和罚款的单位时间任务调度：n任务，每个都能在单位时间内完成，每个都有对应的完成期限及完成不了的罚款数额，确定执⾏顺序使罚款最少。

（例：智⼒⼤冲浪） 按照罚款数额由⼤到⼩排序，然后依次进⾏安排。

安排规则为：使处理当前任务的时间在既在期限之内，⼜尽量靠后，如果都已经排满，则放弃处理并扔在最后.⼆、⼆分（单调性）与三分（单峰性）⼆分的边界问题：⼆分常见模型：⼆分答案（将最优化问题转为判定性问题），⼆分查找（求解分界点），代替三分（⼆分导函数求极值，定义域通常定为整数域）。

三分：任取两点判断好坏不断缩⼩区间。

三，搜索dfs的优化技巧：优化搜索顺序（对象），排除等效冗余，可⾏性剪枝（上下界剪枝），最优性剪枝，记忆化。

初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)(4)拓扑排序 (poj1094)(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)(6)最大流的增广路算法(KM算法). (poj1459,poj3436)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用.(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513)四.简单搜索(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)(poj1408,poj1584)(4)凸包. (poj2187,poj1113)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983)(2)最小费用最大流(poj2516,poj2516,poj2195)(3)双连通分量(poj2942)(4)强连通分支及其缩点.(poj2186)(5)图的割边和割点(poj3352)(6)最小割模型、网络流规约(poj3308, )三.数据结构.(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)(2)静态二叉检索树. (poj2482,poj2352)(3)树状树组(poj1195,poj3321)(4)RMQ. (poj3264,poj3368)(5)并查集的高级应用. (poj1703,2492)(6)KMP算法. (poj1961,poj2406)四.搜索(1)最优化剪枝和可行性剪枝(2)搜索的技巧和优化 (poj3411,poj1724)(3)记忆化搜索(poj3373,poj1691)五.动态规划(1)较为复杂的动态规划(如动态规划解特别的施行商问题等) (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)六.数学(1)组合数学:1.容斥原理.2.抽屉原理.3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).4.递推关系和母函数.(2)数学.1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)2.概率问题. (poj3071,poj3440)3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)(3)计算方法.1.0/1分数规划. (poj2976)2.三分法求解单峰(单谷)的极值.3.矩阵法(poj3150,poj3422,poj3070)4.迭代逼近(poj3301)(4)随机化算法(poj3318,poj2454)(5)杂题. (poj1870,poj3296,poj3286,poj1095)七.计算几何学.(1)坐标离散化.(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)(3)多边形的内核(半平面交)(poj3130,poj3335)(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)高级:一.基本算法要求:(1)代码快速写成,精简但不失风格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)(2)保证正确性和高效性. poj3434二.图算法:(1)度限制最小生成树和第K最短路. (poj1639)(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446) (3)最优比率生成树. (poj2728)(4)最小树形图(poj3164)(5)次小生成树.(6)无向图、有向图的最小环三.数据结构.(1)trie图的建立和应用. (poj2778)(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和在线算法(RMQ+dfs)).(poj1330)(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的).(poj2823)(4)左偏树(可合并堆).(5)后缀树(非常有用的数据结构,也是赛区考题的热点). (poj3415,poj3294)四.搜索(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.(poj3131,poj2870,poj2286)五.动态规划(1)需要用数据结构优化的动态规划. (poj2754,poj3378,poj3017)(2)四边形不等式理论.(3)较难的状态DP(poj3133)六.数学(1)组合数学.1.MoBius反演(poj2888,poj2154)2.偏序关系理论.(2)博奕论.1.极大极小过程(poj3317,poj1085)2.Nim问题.七.计算几何学.(1)半平面求交(poj3384,poj2540)(2)可视图的建立(poj2966)(3)点集最小圆覆盖.(4)对踵点(poj2079)八.综合题.(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263) 以及补充Dp状态设计与方程总结1.不完全状态记录<1>青蛙过河问题<2>利用区间dp2.背包类问题<1> 0-1背包，经典问题<2>无限背包，经典问题<3>判定性背包问题<4>带附属关系的背包问题<5> + -1背包问题<6>双背包求最优值<7>构造三角形问题<8>带上下界限制的背包问题(012背包)3.线性的动态规划问题<1>积木游戏问题<2>决斗（判定性问题）<3>圆的最大多边形问题<4>统计单词个数问题<5>棋盘分割<6>日程安排问题<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)<8>方块消除游戏(某区间可以连续消去求最大效益)<9>资源分配问题<10>数字三角形问题<11>漂亮的打印<12>邮局问题与构造答案<13>最高积木问题<14>两段连续和最大<15>2次幂和问题<16>N个数的最大M段子段和<17>交叉最大数问题4.判定性问题的dp(如判定整除、判定可达性等)<1>模K问题的dp<2>特殊的模K问题，求最大(最小)模K的数<3>变换数问题5.单调性优化的动态规划<1>1-SUM问题<2>2-SUM问题<3>序列划分问题(单调队列优化)6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)<1>凸多边形的三角剖分问题<2>乘积最大问题<3>多边形游戏(多边形边上是操作符,顶点有权值)<4>石子合并(N^3/N^2/NLogN各种优化)7.贪心的动态规划<1>最优装载问题<2>部分背包问题<3>乘船问题<4>贪心策略<5>双机调度问题Johnson算法8.状态dp<1>牛仔射击问题(博弈类)<2>哈密顿路径的状态dp<3>两支点天平平衡问题<4>一个有向图的最接近二部图9.树型dp<1>完美服务器问题(每个节点有3种状态)<2>小胖守皇宫问题<3>网络收费问题<4>树中漫游问题<5>树上的博弈<6>树的最大独立集问题<7>树的最大平衡值问题<8>构造树的最小环转一个搞ACM需要的掌握的算法.要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红, 发挥自己的长处,这才是重要的.第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。

好像目前还没有这方面题目的总结。

这几天连续看到四个问这类题目的人，今天在这里简单写一下。

这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。

不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。

在数学中，一个矩阵说穿了就是一个二维数组。

一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。

比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。

其中，结果的那个4等于2*2+0*1：下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵：矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。

为什么矩阵乘法不满足交换律呢？废话，交换过来后两个矩阵有可能根本不能相乘。

为什么它又满足结合律呢？仔细想想你会发现这也是废话。

假设你有三个矩阵A、B、C，那么(AB)C 和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。

经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。

操作有平移、缩放、翻转和旋转这里的操作是对所有点同时进行的。

其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。

如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。

利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。

假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。

预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。

经典题目2 给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。

信息学初学者之家月刊OIBH MonthlyOIBH编辑社2009年第3期版权所有，不得随意转载-1-对一道博弈题的研究衡阳市第八中学:皮一凡指导教师:邹毅【题目描述】聪聪和睿睿最近迷上了一款叫做分裂的游戏。

该游戏的规则是：共有n个瓶子，标号为0,1,2,...,n-1，第i个瓶子中装有P[i]颗巧克力豆，两个人轮流取豆子，每一轮每人选择3个瓶子，标号为i,j,k，并要保证i<j,j≤k且第i个瓶子中至少要有一颗巧克力豆，随后这个人从第i个瓶子中拿走一颗豆子并在第j个和第k个瓶子中各放入一颗豆子（注意到j可能等于k，此时就相当于在那个瓶中放入两颗豆子）。

如果轮到某人而他无法按规则取豆子，那么他将输掉比赛。

胜者可以拿走最后瓶中的所有巧克力豆。

两人最后决定由聪聪先取豆子，为了能够得到最后的巧克力豆，聪聪自然希望赢得比赛。

他思考了一下，发现在有些情况下，先拿的人一定有办法获胜，但是他不知道对于其它情况是否有必胜策略，更不知道第一步该如何取。

他决定偷偷请教聪明的你，希望你能告诉他，在给定每个瓶子中的最初豆子数后是否能够让自己最终得到所有巧克力豆，他还希望你告诉他第一步应该如何取，并且为了必胜，第一步有多少种取法？假定瓶子的个数n大于1，且不超过21，最初每个瓶子中的巧克力豆不超过10000个。

时限为1S。

【输入格式】输入文件第一行是一个整数t表示测试数据的组数，接下来为t组测试数据（t≤10）。

每组测试数据的第一行是瓶子的个数n，接下来的一行有n个由空格隔开的非负整数，表示每个瓶子中的豆子数。

【输出格式】对于每组测试数据，输出包括两行，第一行为用一个空格两两隔开的三个整数，表示要想赢得游戏，第一步应该选取的3个瓶子的编号i,j,k，如果有多组符合要求的解，那么输出字典序最小的一组。

如果无论如何都无法赢得游戏，那么输出用一个空格两两隔开的三个-1。

第二行表示要想确保赢得比赛，第一步有多少种不同的取法。

LCA问题2007年08月15日星期三下午 02:08LCA 问题，即 Least Common Ancestors（最近公共祖先）的意思是：给定一有根树，求其两个节点最近的公共祖先；节点的祖先即从节点至根的路径上的节点的集合。

LCA 问题可以转化为 RMQ 问题求解，方法是：从根开始对树进行一次深度优先遍历，每次沿一条边到达另一节点时记录下节点的深度，这样就得到一个序列；对于问题中的两个节点，以它们的首次出现为两端的子序列中的最小值就是最近公共祖先。

规模为n的 LCA 经过转化变成了规模为2n-1的 RMQ，渐进复杂度不变，然后就可以使用 RMQ 的各种方法来解答。

但是即便LCA转换成了RMQ，比较好写的ST之类方法还是O(nlogn)的，在竞赛中更好用的似乎是 Tarjan 的 O(nα(n)) 的离线算法。

算法用到了并查集，在对树的一次深度优先遍历后完成，方法大致是这样的：每次访问到一个节点，对它建立一个并查集，设定它的祖先为自己；访问它的每个子节点，并在每次访问结束后设儿子的并查集的代表顶点的祖先为自己；将自己标记为黑色，对于每个与它有关的问题，若另一节点也为黑色，则这个问题的答案就是另一节点所在的并查集的代表顶点的祖先。

实现时第一次编写错误了，原因是这个算法要求的并查集需要有一点点特殊：每次合并都需要把子节点所在的并查集的代表节点设为父节点所在的并查集的代表顶点而不是相反，否则就会WA。

但这也许还是个好事情呢，如果第一次不WA 也不会注意到这个细节。

至于RMQ转换成LCA其实也简单，要将原数组转换成听上去有点神秘的“Cartesian Tree”（笛卡尔树）。

所谓Cartesian Tree，是一个二叉树，每个节点的值大于子节点（堆序），节点的中序遍历满足原数组顺序（排序二叉树）。

看到这儿我明白了——这不就一Treap么……当然，我们是不用挨个插入 Treap 的O(nlogn) 算法的。

RMQ问题ST算法/*RMQ(Range Minimum/Maximum Query)问题：RMQ问题是求给定区间中的最值问题。

当然，最简单的算法是O(n)的，但是对于查询次数很多（设置多大100万次），O(n)的算法效率不够。

可以用线段树将算法优化到O（logn)（在线段树中保存线段的最值）。

不过，Sparse_T able算法才是最好的：它可以在O(nlogn)的预处理以后实现O(1)的查询效率。

下面把Sparse T able算法分成预处理和查询两部分来说明(以求最小值为例)。

预处理:预处理使用DP的思想，f(i, j)表示[i, i+2^j - 1]区间中的最小值，我们可以开辟一个数组专门来保存f(i, j)的值。

例如，f(0, 0)表示[0,0]之间的最小值,就是num[0], f(0, 2)表示[0, 3]之间的最小值, f(2, 4)表示[2, 17]之间的最小值注意, 因为f(i, j)可以由f(i, j - 1)和f(i+2^(j-1), j-1)导出, 而递推的初值(所有的f(i, 0) = i)都是已知的所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i, j)的值。

查询:假设要查询从m到n这一段的最小值, 那么我们先求出一个最大的k, 使得k满足2^k <= (n - m + 1).于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];而我们之前已经求出了f(m, k)为[m, m+2^k-1]的最小值, f(n-2^k+1, k)为[n-2^k+1, n]的最小值我们只要返回其中更小的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.例如, rmq(0, 11) = min(f(0, 3), f(4, 3))*/#include<iostream>#include<cmath>using namespace std;#define MAXN 1000000#define mmin(a, b) ((a)<=(b)?(a):(b))#define mmax(a, b) ((a)>=(b)?(a):(b))int num[MAXN];int f1[MAXN][100];int f2[MAXN][100];//测试输出所有的f(i, j)void dump(int n){int i, j;for(i = 0; i < n; i++){for(j = 0; i + (1<<j) - 1 < n; j++){printf("f[%d, %d] = %d\t", i, j, f1[i][j]);}printf("\n");}for(i = 0; i < n; i++)printf("%d ", num[i]);printf("\n");for(i = 0; i < n; i++){for(j = 0; i + (1<<j) - 1 < n; j++){printf("f[%d, %d] = %d\t", i, j, f2[i][j]);}printf("\n");}for(i = 0; i < n; i++)printf("%d ", num[i]);printf("\n");}//sparse table算法void st(int n){int i, j, k, m;k = (int) (log((double)n) / log(2.0));for(i = 0; i < n; i++){f1[i][0] = num[i]; //递推的初值f2[i][0] = num[i];}for(j = 1; j <= k; j++){ //自底向上递推for(i = 0; i + (1 << j) - 1 < n; i++){m = i + (1 << (j - 1)); //求出中间的那个值f1[i][j] = mmax(f1[i][j-1], f1[m][j-1]);f2[i][j] = mmin(f2[i][j-1], f2[m][j-1]);}}}//查询i和j之间的最值,注意i是从0开始的void rmq(int i, int j){int k = (int)(log(double(j-i+1)) / log(2.0)), t1, t2; //用对2去对数的方法求出kt1 = mmax(f1[i][k], f1[j - (1<<k) + 1][k]);t2 = mmin(f2[i][k], f2[j - (1<<k) + 1][k]);printf("%d\n",t1 - t2);}int main(){int i,N,Q,A,B;scanf("%d %d", &N, &Q);for (i = 0; i < N; ++i){scanf("%d", num+i);}st(N); //初始化//dump(N); //测试输出所有f(i, j)while(Q--){scanf("%d %d",&A,&B);rmq(A-1, B-1);}return 0;}。

动态序列与动态树问题——浅谈几种常用数据结构天津南开中学莫凡*2014年6月5日要动态序列问题是指给定一个序列，在其上执行一系列在线操作（例如一段数的修改、某一区间的反转或某一区间内的最大值查询等等），是算法竞赛中的常见问题，在生产生活中也具有较强的实用价值。

本文重点通过介绍通过几种常用的平衡二叉树型数据结构解决动态序列问题。

动态树问题是动态序列问题的延伸，支持一棵树（或是一片森林）的点上、边上信息的维护以及形态的变换。

由于动态树问题将维护的对象由序列拓展成一棵树，故其在图论中具有重要的实用价值。

由于时间仓促，加上作者水平过弱，不足之处请多多指正。

本文涉及的数据结构虽然都非常简单，但是并不适合初学算法与数据结构的读者，阅读这篇文章的前提条件只有一个：所有涉及的问题你都可以用暴力实现*作者邮箱：w007878@1IndexI几种常用的数据结构41线段树41.1线段树概况 (4)1.2线段树的修改与信息合并 (5)1.3线段树的具体实现与编程细节 (6)1.4另一种实现方式 (6)1.5适用范围 (8)2伸展树92.1平衡树的旋转机制 (9)2.2伸展——Splay的基本操作 (9)2.3懒标记、区间查询和修改 (10)2.4代码实现（C++） (11)2.5优势与弊端 (12)2.6复杂度分析 (13)3Treap153.1Treap=Tree+Heap (15)3.2基于旋转的的Treap (15)3.3重量平衡树 (15)3.4笛卡尔树 (16)3.5核心代码 (17)4实用技巧174.1静态内存回收 (18)4.2数据结构的嵌套 (18)4.3数据结构的可持久化 (19)II动态序列问题2025第k大数205.1不带修改的 (20)5.2带修改的 (21)5.3带插入的 (21)6一些练习题226.1第k大系列 (22)6.2NOI2007项链工厂 (23)6.3NOI2005维护数列 (23)6.4NOI2003文本编辑器 (24)6.5TJOI2014电源插排（w007878强化版） (24)III动态树267DFS序与树链剖分267.1在海棠花开的年代 (26)7.2Begoina的实现 (27)7.3用剖分找LCA (28)7.4复合问题 (29)8link-cut-tree298.1动态维护的剖分 (29)8.2具体的做法 (30)8.3代码很简单 (30)9子树问题与Toptree319.1基于节点收缩的动态树 (31)9.2仍然是剖分的思想 (31)10练习题们3210.1SDOI2011染色(BZOJ2243) (32)10.2tree(伍一鸣) (32)10.3WC2006水管局长数据加强版（BZOJ2594） (32)IV鸣谢333Part I几种常用的数据结构这一部分着重介绍线段树、Splay、Treap这三种数据结构的实现、复杂度分析以及各自适用的范围。