专栏文章

线段树与势能分析

fflower1
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miog1s8y
此快照首次捕获于
2025/12/02 18:37
3 个月前
此快照最后确认于
2025/12/02 18:37
3 个月前
查看原文

例题

P4145

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

UOJ228

区间开根，区间加。
原本的势能分析将不适用，因为区间加会极大增加势能，因此我们要找到一个势能，使得这个势能受到区间加的影响很小。
观察到两个数开根后，这两个数的差值会迅速减小，在至多 O(log⁡log⁡n)O(\log \log n) 次后两个数就会相同。
但考虑如下数据 8,9{8,9}，开根后会变为 2,3{2,3}，两个数开根后减小的数相同，此时进行区间加法，复杂度就爆炸了，因此我们对这种特殊情况进行特判。
考虑维护线段树每个节点最大值为 mxmx，最小值为 mimi。
  1. 若 mxmx 与 mimi 开根后相同，则直接打上开根标记。
  2. 若 mxmx 与 mimi 开根前后差值均为 11，则打上减法标记。
  3. 其余情况暴力递归。
定义势能为 ∑log⁡log⁡∣ai+1−ai+1∣\sum \log \log |a_{i+1}-a_i+1|。
每次递归开根，区间势能至少减少 11。
每次区间加，势能增加量是 O(log⁡log⁡n)O(\log \log n) 的。
总时间复杂度 O(nlog⁡n)O(n \log n)。

P9989

区间 gcd⁡\gcd。
注意到一个数取 gcd⁡\gcd 后结果自己的因数，所以一个数有效的取 gcd⁡\gcd 次数是 O(log⁡n)O(\log n)。
对于一个数，若其是 xx 的因数，则不需要再操作了。对于一个区间，若区间 lcm⁡\operatorname{lcm} 是 xx 的因数，则无需递归。
时间复杂度 O(nlog⁡2n)O(n \log^2 n )。

HDU5306

区间最值。
考虑如下解法，每个节点维护区间最大值 mxmx，区间次大值 sese 和区间最大值个数 cntcnt。
当区间对 xx 取 min⁡\operatorname{min} 时，分情况讨论：
  1. 当 x≥mxx \ge mx 时，显然操作不会产生影响，直接退出。
  2. 当 mx>x>semx > x > se 时，此次操作只会对区间最大值有影响。将区间和减去 cnt⋅(mx−x)cnt \cdot (mx-x)，打上标记推出即可。
  3. 当 se≥xse \ge x 时，暴力递归合并信息。
接下来我们考虑证明其时间复杂度为 O(nlog⁡n)O(n \log n)。
定义势能为线段树所有节点不同元素种类数的个数。
初始势能为 O(nlog⁡n)O(n \log n)，每次递归下传，至少会减少 11 的势能，因此时间复杂度为 O(nlog⁡n)O(n \log n)。

P10639

区间最值，区间加。
对于区间加用懒标记维护，采用与上题相同的做法即可，并且这种做法的时间复杂度是 O(nlog⁡2n)O(n \log^2 n)。
定义势能为线段树所有与父亲最大值不相同节点的深度和。
对于区间加，至多使得被访问的 O(log⁡n)O(\log n) 个区间增加势能，势能增加量为 O(log⁡2n)O(\log^2 n)。
对于区间取 min⁡\min，考虑递归的叶子节点，有父亲的次大值 ≥x\ge x，其两个子节点次大值 <x< x。那么必然有父亲的最大值和次大值分别是两个儿子的最大值，恰好会有一个儿子势能会减小它的深度即 O(log⁡n)O(\log n)，因此均摊下来每次递归会减小 O(1)O(1) 的势能。
至此我们证明了时间复杂度是 O(nlog⁡2n)O(n \log^2 n)。

P4556

线段树合并。
本体使用线段树合并解决，我们主要分析一下线段树合并的复杂度。
两棵线段树合并时，对于一个节点，若其需要递归合并，当且仅当这两颗线段树都有这个节点，所以每次递归会使节点数减少 11，每次合并的时间复杂度为两棵线段树重合的节点数量。
初始有 O(nlog⁡n)O(n \log n)，的节点，所以时间复杂度为 O(nlog⁡n)O(n \log n)。

CF1515H

值域上区间 and，区间 or，区间 xor，区间求种类数。
考虑使用 0-1trie 解决，可以将其视作一棵动态开点权值线段树，每个线段树结点向左子树连权值为 00 的边，向右子树连权值为 11 的边。
对 and，or，xor 操作进行分析，单独考虑一个叶子节点在操作后会放在什么位置，发现其相当于将一些父亲的左儿子改为右儿子，右儿子改为左儿子。这会改变树的形态，难以在区间上维护。
为了方便操作，我们把需要操作的区间使用线段树分裂分裂出来，操作完再线段树合并回去，这样可以将区间操作转化为全局操作。
由于每次线段树分裂至多新增 O(log⁡V)O(\log V) 个节点，每次线段树合并递归都将减少 11 个节点，所以这部分的时间复杂度为 O(nlog⁡V)O(n \log V)。
xor 操作相当于将线段树对应的层交换左右儿子，可以打全局 tagtag。
and 操作可以 or 和 xor 操作替代，定义 U=220−1U = 2^{20}-1，则 xx &\& yy =((x⊕U)∣(y⊕U))⊕U = ((x \oplus U)|(y \oplus U)) \oplus U。
思考 or 操作后会带来什么变化。
  1. 只有左子树，左子树会放在右子树的位置上。
  2. 只有右子树，没有变化。
  3. 同时具有左子树和右子树，左子树会合并到右子树上。
情况 1，2 可以打 tagtag 维护。情况 3 需要进行线段树合并，这会使节点数至少减小 11，所以如果能定位到所有情况 3 的节点，均摊复杂度就是正确的。
如果子树内有情况 3 的节点，就暴力递归，否则打 tagtag 返回。
这需要判断子树内对应深度是否存在节点同时具有左右子树，容易状压维护的。
实现细节上需要注意 or 标记与 xor 标记的下传顺序。
线段树初始有 O(nlog⁡V)O(n \log V) 个节点，定位单个节点的复杂度是 O(log⁡V)O(\log V)，总时间复杂度 O(nlog⁡2V)O(n \log^2 V)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...