lessons/课程/08-高级线段树与树状数组/04-SegmentTreeBeats与势能剪枝.md

Segment Tree Beats 与势能剪枝

本节目标

理解区间非线性修改为何通常不能直接 Lazy，掌握 Beats 的“最大值、严格次大值、最大值个数”条件更新，并能用势能证明取模、约数替换等递归到叶的操作总复杂度。

前置知识与课前自测

前置：Lazy Segment Tree、摊还分析。

1. 对区间做 a_i=min(a_i,x)，只保存最大值和区间和够吗？
2. 若 $secondMax<x<max$，哪些元素会变化？
3. 区间取模为何看似每次到叶，却仍可能通过最大值剪枝通过？

答案

1. 不够，还需知道最大值有几个以及其余元素的最大值。 2. 只有等于最大值的元素，且它们统一变成 x。 3. `max

问题动机与核心知识

普通 Lazy 要求修改能由节点摘要直接更新，并可安全传给孩子。chmin(x) 在 $secondMax<x<max$ 时只影响最大值组，因此节点可直接更新：

$$ sum\mathrel{-}=(max-x)\cdot countMax,\qquad max\leftarrow x. $$

若 $x\le secondMax$，变化涉及至少两档值，必须下放。这种在节点条件满足时“击败”递归的结构称 Segment Tree Beats。

另一些操作没有固定摘要闭式，但存在稳定点或快速下降势能：取模让被改变值至少缩到原来一半；约数个数函数很快降到 2 并稳定。用节点最大值判整段是否已稳定，剩余有效叶修改总次数受势能约束。

实现指南

• secondMax 是严格次大，不是第二个元素；全相等段设为负无穷。
• 下传时若孩子最大值大于父最大值，对孩子执行同一 chmin(parent.max)。
• 合并时分别处理左右最大值相等/不等，正确累加 countMax。
• 势能剪枝证明要写“每次真正改变下降多少”，不能只说“跑得快”。

精选例题 1：Gorgeous Sequence

来源与题意

• HDU-5306 Gorgeous Sequence，2015 Multi-University Training 2
• 多组总 $n,m\le10^6$；支持区间 chmin、区间最大值、区间和。

Hint 1

节点保存 `max1,max2,countMax,sum`。

Hint 2

整段覆盖且 `max2 < x < max1` 时可只降低最大值组。

Observations

• 修改只区分“大于 x”和“不大于 x”；节点中若大于 x 的只有最大值一档，就能整体处理。
• 直接条件必须是严格 max2<x，等号时两档将合并，摘要不足以更新新最大个数。
• 查询和最大值都由这四个量闭合维护。

Editorial 与正确性证明

递归遇到 max1<=x 直接返回；整段且 max2<x 调整最大组；否则下传父最大约束并递归孩子。直接更新条件保证受影响元素恰是最大值组，因此和、最大值、计数都准确；其他情况递归到能区分值档的位置，最终每个大于 x 的叶都被改且其余不动。

Beats 的严格复杂度分析较细：每次无法整段处理会使节点最大/次大结构发生实质变化，常用势能可证均摊近 $O((n+q)\log n)$ 到 $O((n+q)\log^2 n)$；本题标准实现可通过给定总规模。

核心伪代码与附件

range_chmin(node, x):
    if node.max1 <= x: return
    if fully_covered and node.max2 < x:
        node.sum -= (node.max1-x) * node.countMax
        node.max1 = x; return
    push parent's max constraint to children
    recurse and pull

完整 C++17 附件

精选例题 2：The Child and Sequence

来源与题意

• CodeForces-438D The Child and Sequence，难度 2300
• $n,m\le10^5$；区间和、区间取模、单点赋值。

Hint 1

节点保存最大值与和；若 `max < mod`，整段不变。

Hint 2

其余情况递归到叶做 `%`，再回拉。

Observations

• 取模无法仅凭 sum/max 直接算新和，但 max 能证明整段稳定。
• 若 $x\le a$ 且发生 a%=x，新值严格小于 $a/2$；包括 $x>a/2$ 时余数为 $a-x<a/2$。
• 单点赋值可能提高势能，但每次只增加一个点，可计入操作预算。

Editorial 与证明

区间修改对最大值小于模数的节点剪枝，否则下沉至叶。每个叶真正被取模一次后至少减半，所以在两次赋值之间最多有效修改 $O(\log A)$ 次；每次访问再乘树高，得到 $O((n+q)\log A\log n)$ 的安全上界。查询与赋值为普通 $O(\log n)$。

核心伪代码与附件

range_mod(node, x):
    if disjoint or node.maximum < x: return
    if leaf: value %= x; return
    recurse to children; pull sum and maximum

完整 C++17 附件

精选例题 3：SUM and REPLACE

来源与题意

• CodeForces-920F SUM and REPLACE，难度 2000
• $n,m\le3\times10^5,a_i\le10^6$；区间把 $a_i$ 替换为正约数个数 $D(a_i)$，以及区间和。

Hint 1

$D(1)=1,D(2)=2$，值不超过 2 后永久稳定。

Hint 2

节点最大值不超过 2 时整段跳过。

Observations

• 约数函数不单调到“每次减半”，但 $10^6$ 范围内迭代极快进入 2。
• 可先筛法预处理所有 $D(x)$，叶修改 $O(1)$。
• 最大值是稳定性证书；区间和用于回答查询。

Editorial 与正确性证明

筛法为每个约数 $d$ 给倍数加一，得到 divisor_count。替换操作在 maximum<=2 的节点停止，否则递归到叶替换。被跳过段所有元素确为不动点；未跳过段最终访问每个尚不稳定叶并精确更新。每点有效变化次数为很小的 $O(\log\log A)$，总访问均摊可控。

核心伪代码与附件

precompute D[x] for x <= 1e6 by divisor sieve
replace(node):
    if node.maximum <= 2: return
    if leaf: value = D[value]; return
    recurse; pull sum and maximum

完整 C++17 附件

灵活性训练

CodeForces-679E Bear and Bad Powers of 42（3100）维护区间加/赋值，并反复避开坏值 $42^k$。它要求节点保存到下一个坏值的最小距离，在触碰阈值时局部修复；用于训练“维护下一次结构变化的时间”，不作后续前置。

扩展与联系

Beats 不是任意非线性修改的万能模板。能否使用取决于：节点是否能识别少数受影响值档、直接更新后摘要是否闭合、失败下沉是否有势能保证。

总结与自检

1. max2<x 为什么必须严格？
2. Beats 下传的父约束是什么？
3. 取模有效修改为何至少减半？
4. maximum<=2 为什么是约数替换的充分剪枝？

课后训练建议

先把 Beats 与朴素数组对拍，随机操作刻意令 x 等于次大值。势能题记录每个叶实际被访问次数，观察上界而非只看总耗时。