线段树

线段树把索引区间递归二分，每个节点预存其规范区间的聚合摘要。任意查询区间可分解为 $O(\log n)$ 个互不重叠的规范节点并快速重组，点更新则只影响一条根路径；结合律保证不同分解方式得到同一结果。它不是按数值“线段”排序，而是维护离散索引区间的树形覆盖。

Fenwick 树理路Fenwick 树Fenwick tree · Binary indexed tree用二进制最低位分解维护动态前缀聚合，支持单点更新与前缀查询的对数时间数据结构。用二进制低位分解维护前缀可逆聚合，空间和常数更小，但难以表达任意可合并懒标记；稀疏表理路稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。面向完全静态的幂等查询，预处理后可常数回答 RMQ，却不支持在线更新。线段树以更大常数换取通用区间分解和更新能力。

区间和、最小值、最大子段信息都可通过设计合并规则维护。合并必须结合；非交换运算还必须保持左右顺序。普通线段树不自动支持任意区间更新。

数组 $[2,1,4,3]$ 的根保存总和 $10$，左右子分别保存 $3,7$。查询闭区间 $[2,4]$，组合下标2的叶值1与节点 $[3,4]$ 的和7，得到8；把位置3改为5后，叶、右半区间与根的摘要依次变为5、8、11。

要实现返回最左最小位置的零基半开 RMQ 接口，须另选保存下标的摘要：本页第 $j$ 个叶保存 $(a_j,j)$，两份非空摘要按字典序取最小值，键并列时保留较小下标。再加入一个表示空摘要的独立标记 $e$，规定 $e\circ z=z\circ e=z$；它在最小值选择中让位于每个真实数对，无需假设键集合含数值 $+\mathrm{\infty }$。查询 $[l,r)$ 对应本页的闭区间 $[l+1,r]$，取返回数对的下标分量再减一。

静态区间和可用前缀相减回答，线段树则保留点更新后继续查询的能力。懒惰区间更新还要求更新标签能复合，并且标签作用与节点摘要、区间长度之间有可在 $O(1)$ 时间维护的兼容规则；“给区间做任意修改”不满足这一条件。大范围稀疏坐标可用动态开点或坐标压缩。

数组理路数组Array以连续整数下标支持随机访问的有限序列结构。提供叶序，二叉树理路二叉树Binary tree由空树或根节点及左右两个子树槽位递归组成的有限结构；单孩子所在的左右位置也属于树形。提供区间分解，幺半群理路幺半群Monoid具有双侧单位元的半群。提供结合聚合；懒惰传播理路懒惰传播Lazy propagation把作用于整个节点区间的可组合更新暂存为标记，仅在必要时下传。在满足上述标签条件时增加区间更新。在线 RAM 中，标准静态布局占 $O(n)$ 空间，构建 $O(n)$，查询与合法更新为最坏 $O(\log n)$。

线段树的节点摘要也是树增强理路搜索树增强定理与方法Search-tree augmentation区分可逐层重算的子树摘要与旋转后只需局部修复的中序聚合，并据此维护增强搜索树。思想，但索引骨架固定，不是按键旋转的搜索树。重链分解理路重链剖分heavy-light decomposition · HLD按子树大小选择重儿子，把树路径拆成对数条连续链区间。把树路径拆成若干数组区间后调用线段树；持久化数据结构理路持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。则通过路径复制保留历史根。

平方根分解理路平方根分解Square-root decomposition · Sqrt decomposition · 根号分解将数组分成可维护的连续块，在两端直接扫描、中间整块查询，并按摘要能力核算更新与块长。采用一层连续块而非递归区间树。保存每块排序表后，可以在线处理点赋值和区间阈值计数，但一次赋值要移动块内数组项，查询还要为每个整块付二分成本；不能把本页常数摘要的对数界直接搬过去。

树套树可在每个外层节点再维护一套内层索引，服务二维正交查询，但空间和更新代价必须把两层同时计入。线段树分治处理的是另一条轴：它把对象的有效时间段分配给时间树上的规范节点，DFS 进入、退出节点时配合可回滚结构回答离线动态问题。

区间树理路区间树Interval tree · Centered interval tree按中心点递归分配区间，用两套端点次序实现静态点刺与交叠报告，并区分固定坐标骨架的动态成本。存储的是一组几何区间并回答 stabbing/intersection 查询，不能与“把数组区间递归分解”的本页结构同名互换。

Li Chao 树理路Li Chao 直线树Li Chao tree · Li Chao segment tree把离散查询坐标递归二分，每个结点保留中点胜者，把另一条线送往唯一仍可能获胜的半边。也递归二分查询坐标，但每个结点保存一条参与下包络竞争的线。插入时保留中点胜者，把另一条线送到单侧；查询比较根叶路径上的线值。这套正确性来自两条线至多交一次，不是把子区间摘要用结合运算合并。