线段树

线段树把索引区间递归二分，每个节点预存其规范区间的聚合摘要。任意查询区间可分解为 $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$ 与节点 $[3,4]$ 得 $8$；把位置 $3$ 改为 $5$ 后沿叶到根更新三个摘要。

区间和差可用前缀和静态回答，但线段树支持在线更新。聚合若不结合，节点合并次序会影响结果；非交换操作仍可使用，只要严格保留左右顺序。懒惰区间更新还要求更新标签能复合，并且标签作用与节点摘要、区间长度之间有可在 $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更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。则通过路径复制保留历史根。

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

区间树公理库区间树Interval tree · Centered interval tree按中心点递归存放跨中心区间，并以两套端点次序支持动态区间集合上的 stabbing 与交叠报告查询。存储的是一组几何区间并回答 stabbing/intersection 查询，不能与“把数组区间递归分解”的本页结构同名互换。