算法 · 进阶 · 前置：数组、区间与二叉树 · 约 28 分钟
线段树：把区间拆成可合并的节点
不再试图“减去”一个最小值。用层层对半的区间树，直接拼出查询范围。
目标 [2,7) · 已取 0 块 · 合并 +∞
框宽＝区间长度；框内＝最小值。橙框 / 下一步，绿框 / 已取或已更新，虚线 / 已跳过。
0/9 · [0,8) 仅部分相交，拆成左右孩子，继续判断。
滑块支持方向键和 Home / End；边界越过另一端时会带动另一端，始终保持 l≤r。改变输入或模式会重置步骤。赋值每轮从原数组开始，不累计。减少动画模式关闭播放，单步仍可用。
同一步，对照算法
query(node, l=2, r=7)
if disjoint: return +∞
if fully covered: return node.min
return min(query(left), query(right))
// 下一动作：[0,8) · split
// 已取 0 块，合并值 +∞这是递归算法的教学伪代码；图中事件日志为了回放而预先生成，不把日志生成的开销算作单次操作复杂度。
先想一想：最小值从 −4 改成 9，祖先可以都加 13 吗？
不行。只给叶子赋值，再逐层取左右孩子的 min。[4,6) 从 −4 变成6，[4,8) 变成2，全局最小值变成−2；各层变化不等于同一个增量。
再进一步：带着累积和在线段树上找边界
独立的求和舞台，不沿用上面的有符号 min 树。给定非负数组，从 L 向右找第一个使累计和达到 t 的元素。max_right 返回的是仍满足 sum<t 的最大半开边界 R；若 R<n，失败元素正是 A[R]，不在已接受区间里。
修改会保留当前数组并重新开始搜索；这里只观察修改后的搜索路径，不逐步演示更新操作。所有数值非负，阈值必须大于 0。当前 A=[2, 0, 3, 1, 4, 0, 2, 1]。
已接受 [0,0) · acc=0 < t=7
框内＝区间和，框宽＝区间长度；橙框＝下一动作，绿框＝已接受，虚线＝起点左侧跳过。下方条带随接受的整块向右增长。
边界搜索 0/5 · 0+13≥7：整块装不下，向下拆开，先左后右找第一片失败叶子。
滑块支持方向键、Home / End；按钮支持 Tab 与 Enter。切换输入/预设停止播放并重置步骤，上一步可回看；减少动画模式不自动播放。绿色带和橙色指针的移动只是状态过渡，不表示接受了尚未完成的动作。
与图同步的搜索步骤
max_right(L=0, sum < 7)
acc = 0
visit(node):
if node.r <= L: skip
if L <= node.l and acc + node.sum < t:
acc += node.sum; R = node.r; return
if leaf: return node.l and stop search
visit(left); if not found: visit(right)
// 下一动作：split
// 已接受 [0,0)，acc = 0
// 完成当前动作后，图与累积和同步更新预先建树及生成教学日志需 O(n) 空间与建树时间；在已维护的树上，一次标准边界搜索为 O(log n)，不是对每个二分中点再做一次 O(log n) 查询。
为什么不能直接把上面的负数数组搬过来？
因为 sum<t 必须随右边界扩展只从真变假，不能再变真。例如 [5,−6,7]、t=4，前缀和 0、5、−1、6 的判断为真、假、真、假。非负输入保证本例单调；一般 max_right 也可使用别的合并规则和单调谓词，并不是一概禁止负数。
看完图，带走这些结论
线段树把数组区间反复分成不重叠的左右两半。叶子保存一个元素，内部节点保存两个孩子的最小值。查询把目标区间拆成若干完整节点，再取这些节点的最小值；单点赋值只需修改叶子并沿祖先重新合并。
适用条件与边界
本课用零基左闭右开[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)。
逐步例子
- A=[5,−2,7,3,6,−4,2,8]。根节点覆盖[0,8)，分为[0,4)和[4,8)；一直分到[i,i+1)叶子。内部节点的值等于两个孩子的min，所以根保存−4。
- 查询[2,7)：[0,8)只部分相交，继续分。[0,2)不相交，返回+∞；[2,4)完全包含，直接取3，不必再看它的叶子。
- 右半边取[4,6)的−4，以及[6,7)的2；[7,8)跳过。三个完整块[2,4)、[4,6)、[6,7)互不重叠且恰好覆盖[2,7)，结果min(3,−4,2)=−4。
- 正确性：不相交节点对目标无贡献；完全包含时该节点已保存整段min；部分相交时，左右孩子是不重叠的完整分割，递归后取min不会丢失元素。每层最多两条边界路径继续拆分，其他完整块直接停止。
- 把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永远删不掉。
- 奇数长度也能建树：区间[L,R)长度大于1时，以M=floor((L+R)/2)切成[L,M)与[M,R)，两边非空且长度更小。不要求n为2的幂，本课递归结构不填充虚拟元素。
- 边界搜索例子：换用独立非负数组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，但不包含在绿色区间里。
- 边界搜索不变量：acc始终等于已接受连续区间[L,R)的和。起点左侧跳过；整块相加仍小于t就接受并跳过子树，否则先左后右下钻，找到失败叶后立即停止。非负数使谓词sum<t随右端扩展只能从真变假，所以不会错过更早失败位置。t>0保证空段sum=0满足谓词。
- 边界与无解：若首项已经达到阈值，返回R=L，接受空段；零值仍可接受；若剩余全部元素仍不足t或L=n，返回R=n，这不是可访问的元素下标。若题目要一基的首次达标位置，答案为R+1，无解按该题约定为n+1。
- 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 算法讲习会比赛，不代表今天的新热点或可核实搜索热度。