log数据结构专题

前言

log的数据结构，有哪些？

这里的定义并不严格，涉及到log就行，就算复杂度可能有sqrt

主流：

线段树/BIT (SGT-Beats) (LiChaoTree)
平衡树
上述结构互相嵌套（树套树）
上述结构可持久化
树剖
(Link Cut Tre) (这个是NOI大纲的10级算法)
特殊：trie(维护整数)

少见：

笛卡尔树
堆 / 左偏树

如果只是板子，相信大家都会打。

本篇在板子的基础上，讨论如何去应用这些工具。

（注：课件里的东西我还没补完，这里的内容并不全qaq）

线段树/BIT

线段树有很多形式，有些题目中只用到最板子的线段树——这种题一般其它的步骤思维难度大；有些题目要用到线段树的变形，如李超树，吉司机树，或者要用线段树合并等算法，这种题一般思维难度和结构本身的难度都挺大的。

线段树相当于是把分治的过程记录下来了，类似点分树（~~其实应该是点分树类似线段树(小声)~~）

对于连续的一段区间的操作与询问，我们把它拆成若干个区间的整体操作/询问，并合并区间的答案。

lazytag的理解与历史最值

线段树中，我们会用到 lazytag 这个东西。它其实代表的是待进行的操作序列合并后的结果。

在这篇中，我们提到了 lazytag 更深层的理解，并用这个理解搞定了区间历史最值问题。

思维题

前面提到，很多线段树题并不是难在线段树，而是难在如何使用线段树

loj3033：离线，来回贡献

注意到本题没有强制在线。那就可以为所欲为的离线。

首先我们可以把 (|a-b|) 看成 (max(a-b,b-a))，做两遍，然后再取max。然后这个绝对值就废了。

那我们在算一次的时候，不妨只考虑 “前-后” 的情况。

对于一个询问，假设有两个信号塔 (i,j(i<j))。有两个条件要满足，(i) 能到 (j)，(j) 能到 (i)，即，“互相联系”。此时就可以贡献一个 (h_i-h_j)。

像这种一看就不好在线做的题，就先离线再扫描线，是经典的考虑角度。

根据这个套路，把每个询问挂在 (r) 上，然后对 (r) 扫描线。每次处理到一个 (r)，维护一颗线段树，(i) 位置的值表示左端点取在 (i) 的答案。遍历挂在 (r) 上的询问 ([l,r])，查询一下线段树的 (l) 位置就得到答案了。

稍微想一下，对于本题，我们得这样搞：

设线段树的 (i) 位置表示，左边的那个塔恰好在 (i) 位置，(h_i-h_j) 的最大值（注意到“恰好”比较好做）。

那取在 (l) 位置的答案，就是 ([l,r]) 的区间最大值。

由于我们是扫描线的处理，只需要考虑 加入一个位置 (r) 之后线段树如何变化。

根据题意，肯定是和 (r) 位置能互相联系的塔，权值可能要变。问题就在于，如何处理互相联系。对于一个在前面的塔 (i(i<r))，要满足两条：

(i) 能到 (r)
(r) 能到 (i)

然后贡献一个 (h_i-h_r)。我们把 (h_i) 和 (-h_r) 分开来做，即，我们维护俩权值，然后把它俩加起来后求最大值。

②条件非常好搞，区间 ([r-b_r,r-a_r]) 就是 (r) 能到的所有 (i)。

对于①条件，我们这样考虑：假设 (i) 能到 (r)，我们称这个 (i) 是“可用的”。

由于 (i<r)，那 (r) 肯定是要在 ([i+a_i,i+b_i]) 里面才，(i) 才可用。我们发现这玩意类似一个区间加，单点求和的过程（单点求有没有被覆盖到）。如何维护这玩意呢？（自己想一下，很容易想到）

这是一个经典问题，我们把它作一个 “差分”：对于每个 (i)，看成有一个 “开关”。

我们把它打开，(i) 就可用。如果我们不动它，开关状态不变，那 (i) 还是可用的。等我们把它关闭，(i) 才变得不可用。设 “打开”是 (+1)，“关闭”是 (-1)，我们发现开关的打开，关闭，就相当于 (i) 的可用性（0/1）的一个差分。

那我们在 (i+a_i) 的位置加入（vector维护）一个 “打开开关 (i)” 操作，在 (i+b_i+1) 的位置加入一个 “关闭开关 (i)” 的操作。每次到一个 (r)，把 (r) 位置的所有操作都做一遍。那就可以动态的维护哪些 (i) 是“可用”的了。

对于可用的位置 (i)，它的权值就是 (h_i)。而如果 (i) 不可用，那 (h_i-h_r) 的贡献其实是不合法的。我们令它的权值为 (-infin)，就避免了它贡献过来。设这个权值是 (c_i)。即，c[i]=(i可用)?h[i]:-INF。

对于 (r) 能到的位置，还要贡献过去一个 (-h_r) 的权值。我们设这部分的权值是 (c'_i)。

对于一个 (i)，可能有很多 (r) 能到它，我们要找 (h_i-h_r) 最大的。

那它的最优选择肯定是 (h_i+max(-h_r))，也就是线段树维护的 (i) 位置的值。我们设它为 (d_i)。

这部分不太懂的，回去看下线段树维护的是啥。

注意到 ((-h_r)) 这个值，我们只要求最大的那个。那每次 (r) 贡献过去，相当于是区间的 (c') 对 (-h_r) 取 (max)。这样得到的 (c') 就是 (max (-h_r))。那直接令 (d_i=c_i+c'_i)，就是线段树上的答案了。

总结一下，我们的线段树要支持：

单点改 (c)
区间的 (c') 对 (x) 取 (max)
询问 (d=c+c') 的区间最大值

我们似乎不太好处理改 (c) 之后再加上 (c') 最大值如何变化。但其实我们每次改 (c) 的时候，它也许刚变成可用，还没有 (r) 贡献过去，(c') 是 (-infin)；它也许刚变得不可用，那我们显然也不用管它对 (d) 的影响。

那其实不用直接考虑单点改 (c) 对 (d) 的影响，直接 pushup 的时候顺便看一下就行。对 (d) 的影响，我们完全可以在改 (c') 的时候考虑。

对于 (c') 的区间取max，我们可以维护一个lazytag，(t_i) 表示 (i) 节点待处理的操作序列。“操作”就是取max，要合并这个操作序列，显然直接取最大的那个就行。那 (t_i) 就记一个数，表示操作序列里最大的那个。

每次pushdown的时候，更新 (c') 之后顺便更新 (d) 就行。

代码

loj2873：转化

首先把相同的 (a) 合并到一起，然后认为 (a) 是不同的。

我们发现题意的限制就像是一个 “山峰”，讲人话就是，中间大于两边。

考虑如下的构造：

先把 (a) 逆序排
每次插在最左/最右

这样很明显满足山峰的条件。再一想，每一个“山峰”都能用这种方法构造。

于是这样的一种构造就和原题要求的序列等价了。

再考虑另一个问题，有俩排列 (p,q)，每次只能交换 (p) 中相邻俩位置，要换到 (q)，最少几步？

这是个经典题，答案是：排列 (dfrac{p}{q}) 的逆序对数。

注意到排列可以和一个每行每列只有一个 (1) 的矩阵一一对应。

这里排列的除法，看成是变成矩阵，除完之后，再变成排列。

或者说就是，如果把 (q) 重排成 (1,2...n)，(p) 的逆序对数。

那我们每次就看一下插在左边的逆序对多还是插在右边的逆序对多就行了。

为什么这样的贪心是对的呢？因为每一步独立

为什么每一步独立呢？因为我前面不管是啥顺序插，我新来的一个数，都是让以前的所有数一块在它前面/后面，这部分的逆序对贡献，与前面如何排列无关。

然后直接树状数组就可以做。

loj2346：套路转化+线段树

我们发现这个地层的斜向平移非常的不好做。怎么做呢？把坐标轴转个 (45degree)，它就变成了横竖向的平移。

转45°：((i,j) o (i-j,i+j))。

依然不太好做。再发现，地层运动一波之后，最后一次运动的那一根线一定是完整的，而其它的线可能会被切开，变成断断续续的。

自然的，我们顺着这根完整的线，“追溯”回去。

我们可以考虑最后地平线上的状态（即，答案），它们的这些地层是哪里来的？我们可以把操作反过来做，就可以实现这个 “追溯”，然后就可以找到它原来是哪来的。

这有啥用么？那当然很有用，它的深度是多少，答案就是多少！

于是我们把所有的操作反向，把上移改成下移，做一遍之后，原来地表上那些位置最后的深度，就是答案。

转坐标轴之后，设地表上每个点在 ((x,y))。每次操作相当于，对于 (x<k) 的点，(y) 增加 (a)，或者把 (x,y) 换一换。

我们发现每次直线切过来，它“上面”的点都是一段前缀/后缀，所以这个 ((x,y)) 一定都有单调性，可以利用线段树的结构二分得到长度。

实现细节：我们不需要得到长度之后再做区间加，我们可以直接一边二分一边打tag。顺便，需要比较精细的推式子。

代码

维护出入信息

出入信息就是指，对于一个区间，我们记 “以xxx进入区间，走一遍区间，出去之后的结果”。

对于线段树这种树结构稳定，区间划分的均匀的结构，特别适合维护这种信息。

经典题如 NOI2004起床困难综合症，但那个题不需要线段树，是维护的一个全局出入信息。如果那个题变成区间做，就拿线段树做。

口胡题

有 (n) 个运算，用 ((o,x)) 表示。(o) 是运算符，(o=1,2,3,4,5,6,7) 对应加，减，乘，除，and，xor，or 运算。(x) 是运算数，(x<16)，每次运算的结果都只保留二进制后 (4) 位。

你要支持若干询问，每次给定 (l,r,x)，问输入一个 (x)，并依次（即，一个一个做，不合在一起，不用考虑优先级）进行区间 ([l,r]) 中的运算，问最后的 (x) 是多少。输入的 (x<16)。(nle 10^5)。

线段树维护：对于每个区间 ([l,r])，记一下 ([0,15]) 中的每个数进入这个区间算一遍，结果是多少。结果的范围还是 ([0,15])，所以区间信息显然可以合并。

然后就是sb题。复杂度 (O(15nlog n))。

CF712E

见这里

我们用线段树维护了从左边进入区间，从右边出来的概率。这就是一个 “出入信息”。然后还有一个反向的：从右边进入区间，从左边出来的概率，用来合并俩区间。再结合一波推式子之后就可以线段树做了。

Segment Tree Beats!

这个名字来源于吉如一选手（吉老师）的课件。

这种结构可以维护区间对某个数取min的操作。没有区间加操作时，复杂度是严格 (O(nlog n))。

当存在区间加操作时，吉老师的单log证明假了，现在只能证明出 (O(nlog^2 n))，但实际速度接近 (O(nlog n))。

模板题见 bzoj4695

CF1290E：经典套路+吉老师树维护

根据笛卡尔树的基础知识，(i) 位置的size就是 (nex_i-pre_i+1)，其中 (pre_i,nex_i) 分别表示向前/向后第一个比 (i) 大的位置。我们把这个东西求和。

如果后面没有大的，(nex=n+1)；如果前面没有大的，(pre=0)。

注意到它完全可以拆开求。然后再注意到 (nex) 和 (pre) 就是反一反（之后推一下式子即可）。于是问题变成了求 (nex) 的和。

我们能够预先知道每个数最终在哪里，我们直接把它们放在最终位置，在空的位置上补 (0)。则插入就变成了修改一个为 (0) 的位置。考虑每次插入之后 (nex) 如何变化。

设插入 (i) 的最终位置为 (p)，在当前子序列里的位置是 (q)。(q) 可以用树状数组求得。

很明显的是，(p) 后面都被挤了一位，那它们的 (nex) 都 (+1)。

另外，(i) 之前插的数是 ([1,i-1])，它们都比 (i) 小。那 (p) 之前的数， (nex) 应该都不会越过 (i)，所以对 (q) 取 (min)。

(p) 位置本身的 (nex) 是 (i+1)，显然。

因此我们要支持，区间加，区间取min，区间求和。写一个吉老师树就行了。

uoj515：换维度考虑(扫描线)+吉老师树(带扩展)

我们要维护不同的后缀最小值个数。还要支持单点修改。

我们把图画在草稿纸上。对于每次修改，我们用一个类似“可持久化”的东西，把它改掉的位置新建一个副本，写在原来的序列下面，而不是直接涂改掉。

然后我们就发现，我们其实并不需要一行一行考虑（即，顺序维护每次操作），而是可以按列考虑，似乎也很有规律。

即，我们对下标做扫描线，设当前枚举到 (p)，从 (n) 到 (1)。线段树的第 (i) 个位置，维护第 (i) 个时刻 (p) 位置的后缀最小值（记为 mn）是多少，以及它有多少段不同的后缀min（记为cnt）。每个位置还有个初始值，我们认为这是在 (0) 时刻做了一个修改操作。

我们把一个点有哪些操作记一下。修改是直接覆盖的，所以一个操作只能影响到下一个操作之前，设当前操作在 (t) 时刻发生，下一个操作在 (t') 时刻发生，那它能影响的区间就是 ([t,t'-1])，设这个是它的“影响区间”。

对于一个修改为 (x) 的操作，影响区间为 ([l,r])，对于 ([l,r]) 位置，mn显然要和 (x) 取 (min)。如果它原来的mn严格大于 (x)，就给它cnt的 (+1)。

第一个操作就是吉老师树。对于第二个操作，我们也可以借助吉老师树顺便维护：

对于一个区间，我们记它的最大值是多少（mx），以及它出现了多少次（mxcnt），这是最基本的。

对于一个取min操作，如果它正好在次大和最大之间，就直接令 mx=x，然后 cnt+=mxcnt 即可。

这很明显，因为最大值有 mxcnt 个，它们一定都被取min了，所以被取min的次数就新增了 mxcnt 个。

然后就可以打tag，递归处理了。

线段树合并

这是一个经典技巧。通常可以解决集合的“并”问题。它与启发式合并的区别在于，它只有一个log，并且可以顺带的维护很多东西，这是启发式合并所做不到的。

做题的时候，如果发现要维护一个集合，值域比较小（1e5），甚至元素会带个权值，并且要把两个集合合并，并在中途支持一些别的东西，那就可以想到用线段树合并来维护。

下面是一些例题

结合SAM维护right集合

SAM的fail树，可以搞出来一个串的所有后缀。

如果一个串出现了，它的后缀也应该会出现。但如果直接插入的时候放一个 (i) 在集合里，只会在大串里被算一遍，应该把它所有的后缀都算一遍。

转化问题，一个串的right集合等于它fail树上所有儿子right集合的并。

那就可以用线段树合并来搞这个 “并”。

复杂度是 (O(nlog n))。

维护这个之后，就可以做很多较复杂的SAM题。

loj2537

观察题目要求的式子发现，把分布列求出来啥都好做。

观察分布列这个东西的形式：等于值 (x) 的概率为 (P(x))。

我们把叶子权值离散化，那 (x) 的取值就在 ([1,n]) 中，(P(x))看成一个权值：非常像一个线段树的形式。考虑线段树维护分布列。

对于一个点 (u) ，只有一个儿子直接继承即可，考虑有俩儿子 (a,b) 的情况。

在 (a) 中枚举一个 (x)，表示 (a) 权值为 (x)，概率为 (P_a(x))。考虑啥时候 (u) 取到 (x)。

(p_u) 的概率，二者取 (max)，此时的概率为 (P_b(1...x-1))。
(1-p_u) 的概率，二者取 (min)，此时的概率为 (P_b(x+1...n))。

我们发现，要求的本质上是一个 “外部贡献”：(x) 左边的乘一个 (p_u)，(x) 右边的乘一个 (1-p_u)，二者相加，作为一个系数乘给 (x)。

假设线段树合并到了区间 ([l,r])，发现我们可以一边递归区间一边维护区间的“外部贡献” （(a,b) 都要搞）。

比如我们递归到左半边，那就加上右半边乘以 (1-p_u) 的“外部贡献”。

设 (a) 的“外部贡献”，即，(p_u imes P_a(1...l-1)+(1-p_u) imes P_a(r+1...n))，为 (p_a)；同理 (b) 的“外部贡献”为 (p_b)。

如果当前的区间里只有 (a)，那我们就把它整个都乘以 (p_b)。同理，如果只有 (b)，那我们就把它整个都乘以 (p_a)。

然后就可以解决每个位置的 “外部贡献” 了。

像这样就可以一边合并，一边维护额外的权值。最后每个位置的值就是根节点取值的分布列。

代码

可持久化线段树 / 树套树

这俩本质差不多，因为可持久化线段树相当于“前缀和套线段树”

空间复杂度都是和操作的时间复杂度相同的：因为它们几乎每操作一次就要新开一个点。

注：注意是“操作”复杂度而不是查询，比如要查kth你可能要套个二分，那查询的复杂度可能要高。

可持久化

相当于我们可以维护一个结构的每个版本。它有很多应用：

如果信息可减，那我们可以求出一段区间里面的某个结构（权值SGT/TRIE）
版本回退：可以把当前版本的指针指向以前版本，支持版本回退

bzoj3489

详见这里

uoj218

这题大大加深了我对可持久化这玩意的理解。

考虑：如果没有 (2) 操作，就相当于是区间覆盖区间求和。

那如何支持 (2) 操作呢？

我们发现这个 (2) 操作 本质上就是在版本回退。即，我们把每次区间覆盖都新建一个版本，那单点弹栈就相当于把这个点的版本回退到它的上一个版本。

用可持久化线段树维护每个点被 第几次操作 覆盖，并维护点和。

查询某个版本上的一个点被哪个操作覆盖：直接单点查询即可

查询当前某个点的上一个版本：先看它是多少版本，设为 (k)，然后在 (k-1) 版本的树上看看它是多少版本。

这样就相当于把第 (k) 次覆盖操作“skip”掉了，于是就回到了上一个版本

查到上一个版本后，把它的版本改为它上一个被覆盖到的版本，即可。

代码

bzoj3524

首先我们可以求出区间的权值线段树。

但是我们并不能直接维护出哪个数出现次数最多。要是能维护，区间众数也不分块做了。

可以直接减出来的信息是，在一段值域区间里有多少数。

注意到我们只需要查一个出现次数过半的数。这等价于，其它的数就算全都加起来，出现次数也没它多。

那它不管被分到左还是右区间（下面指的都是值域区间），都会有一个明显优势，使它所在的那半区间的数严格大于另一半。

那我们直接在区间的权值树上走，每次走左右中size大的那个，走到最后check一下就行。

复杂度是 (O(nlog n))。

树套树

树状数组套权值线段树，可以维护二维数点问题（绝大多数问题都可以转化）

也可以树状数组套平衡树，空间少一个log，但是时间多好几倍常数

线段树套平衡树，可以解决区间kth问题（少，只有一个板子）

我见到的例题都比较板子，略

平衡树

平衡树，就是在二叉搜索树的基础上加入某种机制使树平衡。那相当于我们有了一个二叉搜索树，并且树高不高。

我们拿它做什么呢？可以用来维护值，就是 pre/nex/kth/rank 之类的（见，普通平衡树）。

对于部分平衡树，如 splay/treap，可以方便的提取区间，就可以用来维护序列（见，NOI2005维护序列）

bzoj3786：维护括号序

括号序：进一个点，放进来（这次称为“左括号）；出一个点，再放进来（这次称为“右括号”）。

很明显左右括号是匹配的。

树的括号序有很多性质，因为它的括号自动匹配，只需要少量修改就可以做很多奥秘操作。

顺便，如果我们把一个点的左括号那边放一个权值，右括号那边放一个负的权值，那一个位置的前缀和就是它到根的路径和。

证：不在栈中的肯定一左一右抵消了，在栈里的只有左括号出现，就正好是它到根的路径

根据这个，我们考虑用平衡树做这题：

对于询问，直接查询前缀和
对于修改链接，我们把子树的区间提取出来，断开原来链接，并插入到新父亲的左括号后面就行
对于子树的修改，我们直接打tag做加法

注意，子树修改的时候，由于某些位置是正权，有些位置是负权，我们需要记哪些位置是正，哪些位置是负，才能够处理。

CF809D：维护dp

见这里

CF573E：维护决策

这个题看起来很dp，确实也容易写出 (O(n^2)) 的dp。而正解需要借助贪心的思想，并结合平衡树做。

有一个结论是，选 (k+1) 个数的最优方案，一定存在一个，包含选 (k) 个数的最优方案。

证明：奥妙重重，我不会证

因此，我们直接一个一个决策就行，按这个说法，一定能够找到其中一个最优解。

这玩意的一个等价表达是，如果某个 (k) 的最优解选了 (i) 位置，那么选 (>k) 个数一定也会选 (i) 位置。

我们枚举 (i)，表示做好了前面 (i-1) 个选啥的决策，平衡树上 (k) 位置表示选 (k) 个的最优解。现在要来搞 (i)。对于当前的 (i)，由上面的等价表达，我们直接在平衡树上二分从哪里开始加，然后需要维护区间平移，区间加等差数列（推式子得）。

区间平移可以借助平衡树的插入的优秀性质，来间接的维护。区间加等差数列，可以维护差分之后变成区间加。

然后就splay搞就行，复杂度是 (O(nlog n))。由于splay的常数很大，我们需要忍一下。

它大概只能跑到 (1e5)，noi.ac上有一个类似的题但那个题数据 (1e6)，我到现在也只过了 (60)

Trie

Trie通常是一种做字符串的数据结构。

我们可以把一个整数，它的二进制形式看成一个串，插入到trie里面。这个trie被称为01trie。

01trie可以方便的搞位运算，也可以很好的维护一个大小关系。

再把它一可持久化，能干的事情还更多

洛谷模板: 可持久化平衡树

我们发现，本题只需要维护整数的大小关系。

用可持久化01trie做就行了。

bzoj3166

这个题稍微需要搞一下。

考虑到这个次大值不太好做，我们考虑钦定它。枚举一个 (i) 位置，钦定它为次大值。

若 (lle ile r)，且 (i) 在 ([l,r]) 中是次大值，那么 ([l,r]) 中必须有恰好一个比 (a_i) 大的位置。

讨论它在左边还是右边。以左边为例，那 ([l,i)) 中应该有恰好一个比 (i) 大的。

设 (i) 左边第一个比 (a_i) 大的位置是 (p_1)，第二个是 (p_2)。那 (l) 应该在 ((p_2,p_1]) 之间。而此时 ([i,r]) 中应该没有比 (i) 大的。类似的，我们设 (i) 右边第一个比 (i) 大的是 (q_1)，第二个比 (i) 大的是 (q_2)，那么 (r) 应该在 ([i,q_1)) 之间。

另一边类似，我们得到结论：([l,r]) 应该是 ([p_2+1,q_1-1]) ，或者 ([p_1+1,q_2-1]) 的子区间。

对于一个固定的 (i) ，区间取的越大，答案肯定不会劣：很明显，原来能选还是能选。

因此，我们并不需要考虑 “子区间” 这个事情，直接拉满：只考虑 ([p_2+1,q_1-1]) 和 ([p_1+1,q_2-1]) 这俩即可。

问题转化为，在一段区间里取一个数，和一个给定的数 (x) 的异或最大。

这是经典题，搞出 trie 即可。那如何搞出 trie 呢？

我们先建一个可持久化trie，第 (i) 个 trie 表示前面 (i) 个数构成的trie。对于区间查询，就 (r,l-1) 俩位置的trie减一下就行了。

复杂度 (O(nlog n))。时间，空间都是。还好本题不卡常，轻松能过。

bzoj2741

本题并不是纯种的log题，还有个分块。

首先我们分块，然后考虑散块和整块。

对于整块，处理 (F(l,r)) 表示第 (l) 个块到第 (r) 个块的答案。枚举 (l)，维护一个trie，就可以做。

对于散块，我们考虑它和其它位置的贡献即可。

左右的散块类似，我们以左边为例。

对于查询 ([l,r])，散块位置 (x (lle xle r))，我们看一下 (x) 作为左端点，([x,r]) 中的某个数作为右端点，最大的异或和。它就是 (a_{x-1}) 与区间 ([x,r]) 中的数的最大异或和，可以用可持久化trie来做。

总的复杂度是 (O(nsqrt{n}log n))。稍微有点卡常，在学校机房里卡了一下午。

怎么只有这么点东西啊

会加的会加的（数据结构题是真做不动，可能会更的较慢qaq）