势能线段树

看《区间最值操作与历史最值问题》 但是没有看懂。于是讨论了一下，总结摘抄至此, 不过我我感觉味道太大了。不是很爽。

Segment Tree Beats：标记类与回收 DFS 复杂度笔记

0. 讨论对象

这里讨论的是区间 chmin/chmax 的复杂度分析。

重点不是普通查询，也不是普通线段树递归，而是：

1

打懒标记以后，可能需要 DFS 回收旧标记。

这个 DFS 单次可能访问很多节点，所以需要证明所有 DFS 的总访问量可控。

1. 104 页的有效标记

104 页先把线段树状态转化成一套“有效标记”。

有效标记的含义：

1

对任意叶子，从叶子向根走，遇到的第一个有效标记决定这个位置的当前值。

冗余标记可以删掉。

所以转化后，整棵线段树最多有 n 个有效标记。

这里的转化主要是分析用的抽象。代码里不一定真的只保留这些标记。

2. 105 页的标记类

105 页继续在有效标记的基础上，把标记按来源分成类。

标记类的定义：

1
2
3
4
5

同一次区间 chmin/chmax 操作产生的标记属于同一类。

同一个标记下传产生的新标记，仍然属于原来的类。

其他标记属于不同类。

所以标记类是按来源分，不是按值分。

同一类标记一般值相同；值相同的标记不一定属于同一类。

3. chmin 什么时候打懒标记

以 chmin(x) 为例。

当前节点维护：

1
2
3
4

mx  = 区间最大值
se  = 区间严格次大值
cnt = 最大值出现次数
sum = 区间和

分三种情况：

1
2
3
4
5
6
7
8

x >= mx:
    当前区间不变，直接返回。

se < x < mx:
    可以在当前节点打懒标记。

x <= se:
    当前节点不能直接处理，需要递归到儿子。

se < x < mx 时，只影响最大值这一层。 其他值都 <= se < x，不会被 min(x) 改变。

所以可以直接更新：

1
2

sum += 1LL * cnt * (x - mx);
mx = x;

这一步在标记视角里，就是在当前节点产生一个新标记。

4. 一次操作产生多少个标记类

一次区间 chmin/chmax 操作产生一个新的标记类。

这次操作可能在线段树上的多个节点停住，并在这些节点打懒标记。

这些标记都属于同一个新标记类。

1
2

一次操作 -> 一个新标记类
多个节点打标记 -> 仍然是同一个标记类

5. 标记什么时候下传

标记下传发生在：

1
2

当前节点有懒标记；
之后的查询或修改需要进入它的儿子。

也就是普通线段树的 pushdown。

在标记类视角里：

1

父亲上的 class C 标记，下传到儿子以后，儿子上的新标记仍然属于 class C。

所以 pushdown 不产生新的标记类，只让已有标记类扩散。

6. 势能的定义

对一个标记类 C，看所有属于 C 的有效标记所在节点。

把这些节点和线段树根节点连起来，得到一棵虚树。

定义：

1

w(C) = C 类标记形成的虚树大小

总势能：

1

Φ = Σ w(C)

也可以等价理解成：

1
2
3
4

如果线段树节点 u 的子树里存在 C 类标记，
则 (C, u) 贡献 1。

Φ 就是所有这种贡献的总和。

这个势能记录的是标记类在树上分布得有多散。

7. 一次 chmin/chmax 增加多少势能

一次区间操作 [L, R] 在线段树上分解成 O(log n) 个规范节点。

这次操作产生的新标记类，初始只出现在这些规范节点上。

这些规范节点来自同一次区间分解，它们和根形成的虚树大小是 O(log n)。

所以一次 chmin/chmax 使势能增加：

1

O(log n)

这里不乘另一个 log n。 原因是这些节点到根的路径大量共享，虚树大小按并集计算。

8. 一次 pushdown 增加多少势能

一次 pushdown 只把某个已有标记类从父亲传到儿子。

父亲和父亲的祖先本来已经在这个类的虚树里。

下传后，新增加的虚树节点只和儿子有关。

所以一次 pushdown 使势能增加：

1

O(1)

粗略理解，最多增加常数个虚树节点。

9. DFS 回收访问一个节点时发生了什么

假设回收 DFS 访问了节点 u。

能够访问 u，说明：

1

u 的子树里存在某个需要被回收的旧标记类 C。

回收之后：

1

u 的子树里不再存在这个 C 类标记。

于是 C 类虚树中至少少了节点 u。

所以：

1

回收 DFS 每访问一个节点，至少让势能 Φ 减少 1。

如果 DFS 同时进入左右儿子，说明左右子树各自都有需要回收的旧标记。 每访问一个儿子，也会对应一次势能下降。

10. DFS 回收总量怎么记账

势能会增加，也会减少。

增加来自：

1
2

1. 新的 chmin/chmax 操作产生新标记类。
2. pushdown 让已有标记类扩散。

减少来自：

1

DFS 回收旧标记。

由于势能始终非负：

1

Φ_final = Φ_initial + 总增加 - 总减少 >= 0

所以：

1

总减少 <= Φ_initial + 总增加

而 DFS 回收每访问一个节点都会让势能至少减少 1，因此：

1
2
3

DFS 回收总访问节点数
<= 势能总减少
<= 初始势能 + 全过程势能总增加

11. 总复杂度

初始有效标记最多 n 个，初始势能计入建树成本。

每次 chmin/chmax：

1

新增标记类带来的势能增加：O(log n)

每次 pushdown：

1

势能增加：O(1)

总 pushdown 次数由普通线段树递归控制，是：

1

O(m log n)

因此全过程势能增加为：

1

O(m log n)

所以所有回收 DFS 的总访问节点数为：

1

O(n + m log n)

再加上普通线段树递归、查询、pushup、pushdown 的成本，整体复杂度为：

1

O(n + m log n)

只看后续 m 次操作的均摊复杂度，可以写作：

1

O(m log n)

12. 当前结论

这段分析要控制的是：

1

所有回收 DFS 总共访问了多少个线段树节点。

核心账本是：

1
2
3

一次 chmin/chmax 增加 O(log n) 势能；
一次 pushdown 增加 O(1) 势能；
DFS 回收每访问一个节点，至少减少 1 势能。

因此，单次 DFS 可以很大，但所有 DFS 加起来不会超过总势能供给。