# 线段树图解：把区间拆成可合并的节点

用二叉区间树看懂区间最小值查询和单点赋值：完整覆盖就取整块，部分相交就继续拆分；沿叶子到根重新合并；另用非负求和树演示 max_right 的整块接受与失败下钻。

原文 / Canonical: https://crazycloud.cc/learn/segment-tree
作者: crazycloudcc
首次发布: 2026-10-19
更新: 2026-10-21

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

线段树把数组区间反复分成不重叠的左右两半。叶子保存一个元素，内部节点保存两个孩子的最小值。查询把目标区间拆成若干完整节点，再取这些节点的最小值；单点赋值只需修改叶子并沿祖先重新合并。

## 适用条件与边界

本课用零基左闭右开[l,r)，0≤l≤r≤n；数组无需有序。演示固定八个有正有负的整数，每次赋值从原数组开始，不累计上轮操作。数学模型支持1到16项、每项−99到99的整数，包含奇数长度且不补叶。空区间没有有限最小值，以+∞作为min的单位元返回；它不是数组中的一个值。主舞台讲点赋值与区间最小值；第二个独立舞台用非负数组演示求和阈值边界搜索。两者都不包含区间修改或懒标记。第二舞台固定8项0到9，阈值1到80，改值保留在当前数组中；底层边界模型允许1到16项0到99及正安全整数阈值。空数组不在本教学模型支持域，L=n的空后缀支持。

## 不变量

每个节点保存它所覆盖区间的最小值，父节点=min(左孩子,右孩子)。查询取出的完整节点互不重叠，最终恰好覆盖目标[l,r)。

## 逐步例子

1. A=[5,−2,7,3,6,−4,2,8]。根节点覆盖[0,8)，分为[0,4)和[4,8)；一直分到[i,i+1)叶子。内部节点的值等于两个孩子的min，所以根保存−4。
2. 查询[2,7)：[0,8)只部分相交，继续分。[0,2)不相交，返回+∞；[2,4)完全包含，直接取3，不必再看它的叶子。
3. 右半边取[4,6)的−4，以及[6,7)的2；[7,8)跳过。三个完整块[2,4)、[4,6)、[6,7)互不重叠且恰好覆盖[2,7)，结果min(3,−4,2)=−4。
4. 正确性：不相交节点对目标无贡献；完全包含时该节点已保存整段min；部分相交时，左右孩子是不重叠的完整分割，递归后取min不会丢失元素。每层最多两条边界路径继续拆分，其他完整块直接停止。
5. 把A[5]从−4赋值为9：先改[5,6)叶子，再重算[4,6)=min(6,9)=6、[4,8)=min(6,2)=2、[0,8)=min(−2,2)=−2。不能给所有祖先都加13，也不能只把祖先与9取min，否则旧的−4永远删不掉。
6. 奇数长度也能建树：区间[L,R)长度大于1时，以M=floor((L+R)/2)切成[L,M)与[M,R)，两边非空且长度更小。不要求n为2的幂，本课递归结构不填充虚拟元素。
7. 边界搜索例子：换用独立非负数组A=[2,0,3,1,4,0,2,1]，L=0，t=7。节点存sum而非min。先接受[0,4)的整块和6；加入[4,8)会达到阈值，继续拆开，最终A[4]=4不能加入。max_right返回R=4：已经接受的是[0,4)，首次失败元素下标也是4，但不包含在绿色区间里。
8. 边界搜索不变量：acc始终等于已接受连续区间[L,R)的和。起点左侧跳过；整块相加仍小于t就接受并跳过子树，否则先左后右下钻，找到失败叶后立即停止。非负数使谓词sum<t随右端扩展只能从真变假，所以不会错过更早失败位置。t>0保证空段sum=0满足谓词。
9. 边界与无解：若首项已经达到阈值，返回R=L，接受空段；零值仍可接受；若剩余全部元素仍不足t或L=n，返回R=n，这不是可访问的元素下标。若题目要一基的首次达标位置，答案为R+1，无解按该题约定为n+1。
10. CSES Dynamic Range Minimum Queries采用一基闭区间[a,b]，应转换为本课零基[a−1,b)；赋值位置k转换为k−1。原题值为正数，本课用负数只是展示min同样适用，不是原题约束。

## 复杂度、合并规则与数值边界

自底向上建树O(n)，保存2n−1个有效节点，空间O(n)。树高O(log n)，点赋值只沿一条祖先链，区间查询每层只沿左右边界继续拆分，二者O(log n)，假设一次min为O(1)。可推广到满足结合律且有单位元的运算，例如和的单位元0、最小值的单位元+∞；不要求可逆。若运算不交换，仍必须按左到右顺序合并。边界搜索在已有求和树上直接跳过整块并沿失败路径下钻，标准实现O(log n)，避免外层二分配合区间查询的O(log² n)。本例sum<t必须非负且t>0；这不是所有max_right谓词的统一取值限制。最大模型总和为16×99=1584，安全整数内精确。交互模型会重新建树并生成回放日志，以小数组换取每步可见；这不代表演示组件本身每次渲染为O(log n)。CSES值≤10⁹，min不做求和，不会产生更大的值；C++可用numeric_limits<long long>::max()作哨兵，必须保证不小于合法值，别拿0当最小值单位元。

## 常见误区

- 将两个前缀最小值相减：例如[1,8,6]与[1,9,7]的前缀最小值全相同，却有不同的后两项最小值。min没有求和那样的逆运算。
- 只判断节点与目标有交集就拿整块：节点可能包含目标之外的更小值。只有完全被目标包含时才能停止下钻。
- 把点赋值当点增加：set(p,u)直接替换原值，父节点必须从两个孩子重新求min；旧最小值变大时尤其不能只做min(old,u)。
- 混淆[l,r)与[l,r]：右端r不取。空区间l=r的返回值+∞表示合并单位元，不声称其有有限最小值。
- 把树形图的框宽当最小值大小：宽度只编码覆盖元素的数量，框内数字才是该段的最小值。
- 本课没有懒标记：给一整段赋值或加数需要额外设计，不能直接套单点赋值路径。

## 自测

查询整个数组需要下钻所有叶子吗？空区间返回0正确吗？把A[5]从−4改成9以后，全局最小值是多少？

不需要，根完全被包含，直接读取根。空区间不能返回0，否则正数区间合并时会错误得到0；本课返回+∞。赋值后全局最小值是−2，需要沿叶子到根重算，而不是给祖先统一加13。

## 进阶 FAQ：满足结合律，为什么仍不能交换左右？

结合律只允许改变括号，不允许改变元素次序。min 恰好还满足交换律，因此左右交换看不出区别；线段树的一般合并规则不能依赖这个巧合。下面是静态延伸例子，第一个主舞台演示区间最小值与点赋值，第二个舞台演示求和阈值边界搜索；这里不把逆序对当成已经实现的交互。

设数组值只可能是 0、1、2。逆序对是满足 i<j 且 A[i]>A[j] 的位置对；相等值不计入。每段保存 (c₀,c₁,c₂,inv)：三个值的出现次数，以及段内逆序对数。空段摘要为 (0,0,0,0)，是合并单位元。

把左段 L 接在右段 R 前面，各频数直接相加。新的逆序对恰分为 L 内部、R 内部、跨界三类，所以 inv(LR)=inv(L)+inv(R)+c₁(L)c₀(R)+c₂(L)[c₀(R)+c₁(R)]。跨界项只数左值大于右值的组合，不包含相等值。

例如 L=[2,1]、R=[0,1]。左段内部有 1 对，右段内部为 0；跨界有 1×1+1×(1+1)=3 对。因此 LR=[2,1,0,1] 的逆序对数为 4。交换左右得到 RL=[0,1,2,1]，却只有 1 对。频数相同，不代表逆序对数相同。

为什么仍有结合律？(L 合并 M) 合并 R 与 L 合并 (M 合并 R) 都是同一串 LMR 的摘要。每一对位置要么同属一段，要么跨越段界，总被恰好计入一次；改变括号不会改变位置先后。但交换成 RML 已是另一串，不能用结合律证明答案相同。

在固定三个取值的前提下，摘要大小与一次合并都为 O(1)，因此点赋值与区间查询仍可 O(log n)。查询必须按从左到右的顺序合并；迭代查询若使用左右两个累积器，新取出的右侧块要放在右累积结果前面，最后再把左累积结果接到右累积结果前面。

实现时频数乘法和 inv 都要使用足够宽的整数，并在乘法前完成宽类型转换。一般长度 n 的数组至多有 n(n−1)/2 对；n=200000 时这个通用上界为 19,999,900,000，已超过有符号 32 位整数。这里仅用通用上界说明类型选择，不声称只有三个值时一定能达到它。

这不是任意区间更新模板：本例只说明顺序敏感的合并与点赋值。若要给整段替换值或做映射，还需另行设计摘要与懒标记，不能直接套用当前主舞台。相关练习来源是 2026-10-12 已结束的 AtCoder 算法讲习会比赛，不代表今天的新热点或可核实搜索热度。

## 参考资料

- [AtCoder AAL001C（比赛2026-10-12）：区间和达到阈值的位置查询](https://atcoder.jp/contests/aalc001/tasks/aalc001_c)
- [AtCoder AAL001C官方题解：线段树边界搜索](https://atcoder.jp/contests/aalc001/editorial/27177)
- [AtCoder 算法讲习会比赛 001（2026-10-12）：D 与官方讲解，三值逆序对合并](https://atcoder.jp/contests/aalc001/tasks/aalc001_d)
- [AtCoder 官方讲解：顺序敏感的逆序对摘要](https://atcoder.jp/contests/aalc001/editorial/27172)
- [CSES：Dynamic Range Minimum Queries（点赋值与区间最小值，常青练习）](https://cses.fi/problemset/task/1649/)
- [AtCoder Library：Segtree（结合律、单位元、set与左闭右开prod）](https://atcoder.github.io/ac-library/production/document_en/segtree.html)

[返回图解实验室](https://crazycloud.cc/learn)