线段树与势能分析

· · 算法·理论

例题

P4145

区间开根。

观察到一个数可以开根的次数为 O( \log \log n)，我们定义势能为所有数可以开根的次数，每次线段树递归开根都将减少 1 的势能，因此每次只需要将需要开根的数开根，时间复杂度 O(n \log n)。

UOJ228

区间开根，区间加。

原本的势能分析将不适用，因为区间加会极大增加势能，因此我们要找到一个势能，使得这个势能受到区间加的影响很小。

观察到两个数开根后，这两个数的差值会迅速减小，在至多 O(\log \log n) 次后两个数就会相同。

但考虑如下数据 {8,9}，开根后会变为 {2,3}，两个数开根后减小的数相同，此时进行区间加法，复杂度就爆炸了，因此我们对这种特殊情况进行特判。

考虑维护线段树每个节点最大值为 mx，最小值为

1. 若 $mx$ 与 $mi$ 开根后相同，则直接打上开根标记。 2. 若 $mx$ 与 $mi$ 开根前后差值均为 $1$，则打上减法标记。 3. 其余情况暴力递归。 定义势能为 $\sum \log \log |a_{i+1}-a_i+1|$。 每次递归开根，区间势能至少减少 $1$。 每次区间加，势能增加量是 $O(\log \log n)$ 的。 总时间复杂度 $O(n \log n)$。 ### P9989 区间 $\gcd$。 注意到一个数取 $\gcd$ 后结果自己的因数，所以一个数有效的取 $\gcd$ 次数是 $O(\log n)$。 对于一个数，若其是 $x$ 的因数，则不需要再操作了。对于一个区间，若区间 $\operatorname{lcm} $ 是 $x$ 的因数，则无需递归。 时间复杂度 $O(n \log^2 n )$。 ### HDU5306 区间最值。 考虑如下解法，每个节点维护区间最大值 $mx$，区间次大值 $se$ 和区间最大值个数 $cnt$。 当区间对 $x$ 取 $\operatorname{min}$ 时，分情况讨论： 1. 当 $x \ge mx$ 时，显然操作不会产生影响，直接退出。 2. 当 $mx > x > se $ 时，此次操作只会对区间最大值有影响。将区间和减去 $cnt \cdot (mx-x)$，打上标记推出即可。 3. 当 $se \ge x$ 时，暴力递归合并信息。 接下来我们考虑证明其时间复杂度为 $O(n \log n)$。 定义势能为线段树所有节点不同元素种类数的个数。 初始势能为 $O(n \log n)$，每次递归下传，至少会减少 $1$ 的势能，因此时间复杂度为 $O(n \log n)$。 ### P10639 区间最值，区间加。 对于区间加用懒标记维护，采用与上题相同的做法即可，并且这种做法的时间复杂度是 $O(n \log^2 n)$。 定义势能为线段树所有与父亲最大值不相同节点的深度和。 对于区间加，至多使得被访问的 $O(\log n)$ 个区间增加势能，势能增加量为 $O(\log^2 n)$。 对于区间取 $\min$，考虑递归的叶子节点，有父亲的次大值 $\ge x$，其两个子节点次大值 $< x$。那么必然有父亲的最大值和次大值分别是两个儿子的最大值，恰好会有一个儿子势能会减小它的深度即 $O(\log n)$，因此均摊下来每次递归会减小 $O(1)$ 的势能。 至此我们证明了时间复杂度是 $O(n \log^2 n)$。 ### P4556 线段树合并。 本体使用线段树合并解决，我们主要分析一下线段树合并的复杂度。 两棵线段树合并时，对于一个节点，若其需要递归合并，当且仅当这两颗线段树都有这个节点，所以每次递归会使节点数减少 $1$，每次合并的时间复杂度为两棵线段树重合的节点数量。 初始有 $O(n \log n)$，的节点，所以时间复杂度为 $O(n \log n)$。 ### CF1515H 值域上区间 and，区间 or，区间 xor，区间求种类数。 考虑使用 0-1trie 解决，可以将其视作一棵动态开点权值线段树，每个线段树结点向左子树连权值为 $0$ 的边，向右子树连权值为 $1$ 的边。 对 and，or，xor 操作进行分析，单独考虑一个叶子节点在操作后会放在什么位置，发现其相当于将一些父亲的左儿子改为右儿子，右儿子改为左儿子。这会改变树的形态，难以在区间上维护。 为了方便操作，我们把需要操作的区间使用线段树分裂分裂出来，操作完再线段树合并回去，这样可以将区间操作转化为全局操作。 由于每次线段树分裂至多新增 $O(\log V)$ 个节点，每次线段树合并递归都将减少 $1$ 个节点，所以这部分的时间复杂度为 $O(n \log V)$。 xor 操作相当于将线段树对应的层交换左右儿子，可以打全局 $tag$。 and 操作可以 or 和 xor 操作替代，定义 $U = 2^{20}-1$，则 $x$ $\&$ $y$ $ = ((x \oplus U)|(y \oplus U)) \oplus U$。 思考 or 操作后会带来什么变化。 1. 只有左子树，左子树会放在右子树的位置上。 2. 只有右子树，没有变化。 3. 同时具有左子树和右子树，左子树会合并到右子树上。 情况 1，2 可以打 $tag$ 维护。情况 3 需要进行线段树合并，这会使节点数至少减小 $1$，所以如果能定位到所有情况 3 的节点，均摊复杂度就是正确的。 如果子树内有情况 3 的节点，就暴力递归，否则打 $tag$ 返回。 这需要判断子树内对应深度是否存在节点同时具有左右子树，容易状压维护的。 实现细节上需要注意 or 标记与 xor 标记的下传顺序。 线段树初始有 $O(n \log V)$ 个节点，定位单个节点的复杂度是 $O(\log V)$，总时间复杂度 $O(n \log^2 V)$。