Segment Tree Beats 从最大值剪枝到严格次大值与条件更新
先明确状态与不变量,再对照手算、证明、边界和实现。
章节速览9 节 · 展开选择
438D区间取模已经回答:当修改不能直接作用于摘要时,可以用最大值跳过不变区间,再证明真正变化的次数有限。但它仍把变化落到叶子。下一步能否在部分情形中,直接算出整段的新和?
本文沿普通懒标记→取模剪枝→条件成立才整段更新组织进阶路线,不新增一道竞赛题卡。模型限定为区间chmin与区间求和:chmin(l,r,x)把每个aᵢ改为min(aᵢ,x)。不包含chmax、区间加法或赋值,后文复杂度不能直接推广到这些操作。
先区别两种“取小”
节点最大值变成min(max,x),很容易计算;但元素分别取小后的区间和不能由原和直接推出。比较[9,5,1,1]与[9,4,2,1]:两者和16、最大值9,对4取小后,和分别为10与11。因此sum和max不足以决定新和。
如果知道只有最大值那一组会改变,问题就简单了。[9,9,5,1]对7取小,只有两个9变成7,和从24降为20;5和1原封不动。新增摘要的目的就是辨认这个条件,而不是记住区间完整分布。
本文教学输入使用1起点闭区间,1≤n,q≤200000,初值与阈值在[−10⁹,10⁹]内。负数同样允许;区间和与差值乘数量都使用64位整数。以下图和手算为原创教学数据,不是某个在线评测的官方题面。
四个摘要,两个返回条件
对每个节点维护sum、最大值mx、严格小于mx的最大值se、最大值出现次数cnt。若全段相等,se记作负无穷;它不是排序后第二个元素,[9,9,5,1]的se为5而不是9。
例子[9,9,5,1],三个区域为条件分类,不按数值比例绘制。
查看原图先排除不相交区间。若x≥mx,所有值本来就不大于阈值,直接返回。若节点被目标区间完整覆盖,且se<x<mx,则只有最大组改变,可以整体更新:
sum ← sum − (mx−x)×cnt;mx ← x;se、cnt保持不变。
条件:完整覆盖且se<x<mx。所有量为整数,sum及乘积用64位保存。
若x≤se,摘要无法按B1维护,必须下降。尤其x=se不能放行:[9,9,5,1]对5取小后,最大值5的数量从2变成3,新的严格次大值为1;原来的四个摘要并没有记录“5出现几次”或“5之下是谁”。只改sum和mx会留下错误的cnt与se,后续更新就可能出错。
阈值位于se之上不等于可以修改部分相交节点。摘要描述整个节点,目标只覆盖一部分时仍必须下降,否则会改到区间外。
flowchart TD
A[访问相交节点] --> B{阈值不小于最大值}
B -->|是| C[无变化返回]
B -->|否| D{完整覆盖且阈值大于次大值}
D -->|是| E[仅压低最大组]
D -->|否| F[下传并递归孩子]
F --> G[合并四个摘要]
合并公式为什么有三个分支
两个孩子最大值相等时,父mx为共同最大值,cnt相加,se取两边se的最大值。左mx较大时,父cnt只来自左边,父se=max(左se,右mx);右边对称。sum始终相加。
这是把所有元素分成“等于全局最大值”和“严格小于全局最大值”两组。不要用max(左se,右se)统一处理:最大值较小的那个孩子,其mx正是父次大值的候选,漏掉它会使整段更新条件过宽。
例如左段[9,9]、右段[5,1],左se为负无穷,右se为1;父se必须是5,而不是1。这个反例直接对应合并代码的分支,适合调试时单独核对。
下传没有独立阈值标记,为什么仍然安全
父节点可能已经用B1压低最大组,而孩子摘要仍停留在旧状态。此时父mx就携带了上限:下传时,只对mx大于父mx的孩子执行压顶。
关键不只是“取min可以合成”,还要证明对子节点执行B1的前提成立。父节点当初能整体压到x,是因为父se<x;任何孩子中严格低于父旧最大值的数,都不超过父se。受影响孩子的旧次大值因此也小于x,孩子只有最大组需要改变。若父节点又做了多次合法压顶,最终上限仍高于这些未改变的较小值,结论继续成立。
实际代码的cap函数只接受这类已被证明安全的调用:一类来自完整覆盖与se检查,另一类来自父上限下传。不能把它当作无条件区间更新函数。部分修改或查询进入孩子前先push,回溯时再pull,便不会用旧孩子覆盖新父状态。
flowchart TD
A[父节点持有较低上限] --> B{孩子最大值超过上限}
B -->|是| C[仅孩子最大组受影响]
C --> D[按安全条件压顶]
B -->|否| E[孩子不变]
D --> F[继续访问孩子]
E --> F
手算同一段的连续变化
| 操作 | 实际数组 | sum | mx | se | cnt |
|---|---|---|---|---|---|
| 初始 | 9,9,5,1 | 24 | 9 | 5 | 2 |
| 全段chmin到7 | 7,7,5,1 | 20 | 7 | 5 | 2 |
| 全段chmin到5 | 5,5,5,1 | 16 | 5 | 1 | 3 |
| 位置2至3压到0 | 5,0,0,1 | 6 | 5 | 1 | 1 |
| 全段chmin到−2 | −2,−2,−2,−2 | −8 | −2 | 负无穷 | 4 |
第二次碰到x=se,必须递归后重建计数;第三次是部分覆盖,要先落实父上限再改孩子。最后一次说明负阈值合法,0不能充当“没有次大值”的哨兵。
复杂度:不同值势能,而非减半势能
这里不能照搬438D的“有效变化至少减半”:9可以依次变8、7、6,每次只降1。更直接的进阶视角是统计每个线段树节点覆盖区间里的不同值数量,再把所有节点相加为势能Φ。它用于证明,不在程序中实际维护。
树高O(log n),每层节点区间互不相交,因此每层不同值数量之和至多n,初始Φ=O(n log n)。一次chmin在完整覆盖节点里不会增加不同值数量:它只把阈值以上的不同值合并成至多一个新值。
对一个完整覆盖但不能直接压顶的节点,有x≤se。若x=se,最大值消失并并入已有值,至少少一种;若x<se,至少两个旧值被压成至多一个新值,也至少少一种。每个这种“困难节点”都消耗至少1势能。
只有部分覆盖节点可能增加不同值种类:原值有的在区间外留下,同时区间内引入阈值x,但新值至多一种。一次连续区间更新在每层至多两个部分覆盖节点,因此总共只补入O(log n)势能。未相交节点不变。
于是整个更新序列的困难节点总数为O(n log n+q log n)。递归展开仅发生在困难节点和O(log n)个边界节点上,每次展开至多访问两个孩子,其余访问常数时间停止。加上查询的O(log n),总时间为**O((n+q)log n)**,空间O(n)。这是本文仅chmin与sum操作集合的序列上界,不是每次更新最坏O(log n)。
例如初值为互异递增数、全段压到所有数之下,第一次更新可以访问整棵树,成本Θ(n)。它消耗初始势能,符合总界。若加入区间加法,完整覆盖节点的不同值关系在其他层会怎样变化,需要重新分析;不能复制这里的结论为完整Beats模板背书。
完整C++17教学实现
输入首行为n q,第二行为初始数组。操作0 l r x执行chmin,1 l r输出区间和。环境C++17,仅使用标准库;输入须满足前述契约,不提供非法下标恢复。哨兵远小于允许的最小阈值,避免与真实值混淆。
1 |
|
迁移前的反例清单
| 误用 | 用什么反例检查 |
|---|---|
| 次大值允许等于最大值 | [9,9,5,1]应得到se=5 |
| 整段条件写成x≥se | 先压到5再压到3,计数必须跟着合并 |
| 忽略右孩子最大值 | 左[9,9]右[5,1]合并后se应为5 |
| 部分覆盖直接改父摘要 | 只改中间两项,检查两端仍保留 |
| 查询前不下传 | 整段压顶后立即查单点 |
| 宣称每次对数 | 递增数组第一次全段压到最小值以下 |
chmin阈值可以合成为较小者,为什么仍不能直接使用普通求和懒标记?
更新函数可以合成,不代表它能由有限摘要计算新和。次大值条件保证只有最大组改变;条件不成立时必须递归。
为什么没有单独的lazy数组?
父最大值本身就是待传给孩子的上限;正确性依赖已证明的孩子次大值条件,并不意味着任意摘要都能这样省略标记。
参考资料与推进范围
- Codeforces:A simple introduction to Segment tree beats:原教程中的停止条件与条件更新思想;本文重新组织限定模型、反例、证明与实现。
- HKOI:Potential Analysis in Data Structures,Ethen Yuen,2024-07-02,含Segment Tree Beats与势能分析。本文明确列出不同值势能如何消耗及补充,不把代码对拍当作复杂度证明。
接下来若扩展到chmin、chmax与加法并存,应重新设计最大/最小两侧摘要、标记作用顺序与复杂度论证。先把本篇四摘要和两个安全调用入口解释清楚,再进入更完整的模型。