线段树

线段树是一类分层表示区间的数据结构。本文讨论常用于数组的版本：根代表整个下标范围，每个非叶节点把范围分成左右相邻两段，叶子对应单个元素。节点保存该段的和、最小值或其他可合并摘要，而不是重复存储区间里的全部数据。

合并操作必须满足结合律；通用实现还提供单位元，以表示空区间。求和的单位元是0，求最小值可用适当的无穷大。结合律让不同分组方式得到相同结果，却不要求交换律：若摘要是字符串拼接等有序运算，查询仍必须保留左右顺序。

参考：[1]

一次区间查询将目标拆成少量互不相交的树节点范围。完整落在目标内的节点直接贡献摘要，完全无交集的节点跳过，只有部分相交处继续向下。这样不用逐一访问目标中的每个元素。用半开区间[l,r)表达查询，还能清楚处理空范围和相邻区间的拼接。

单点修改先更新对应叶子，再沿祖先链重新合并，两侧无关的分支不动。AtCoder的实现把叶子容量补到不小于n的二次幂，以数组存树；查询用左右两个累积器保持顺序。在摘要操作为常数时间时，建树为O(n)，单点更新与区间查询为O(log n)，空间为O(n)。

参考：[1] [3]

若要把一整段元素都加上同一个数，逐个修改叶子会损失效率。延迟传播允许先修改一个完全覆盖节点的摘要，同时记录尚未下传给子节点的更新；以后必须进入它的子区间时，再把标记推下去。延迟的是内部展开，不是让查询返回过期结果。

以区间和为例，节点可存储“总和、长度”。长度为k的区间整体加d后，总和增加d乘k；只存总和而没有长度，就无法直接完成这种更新。多个加法标记可相加，但若同时支持赋值和加法，先赋值再加与先加再赋值不同，必须按真实执行顺序复合。

参考：[2]

通用延迟线段树要求更新映射能作用于摘要，并与左右区间的合并相容；映射集合应包含恒等操作，并对复合封闭。不是任何区间修改都能随意加一个标记而仍保持对数复杂度，设计时要先证明这些条件。若一次摘要合并本身需要O(T)，相关操作成本还要相应乘上T。

线段树适合区间查询与修改交错发生的序列问题。只有静态求和时，前缀和往往更简单；选择结构应服从操作需求。计算几何中也有以线段为对象或处理覆盖关系的树形结构，它们与这里的数组区间聚合版本有关联，却不能仅凭中文名称就视为同一套操作与复杂度。

参考：[1] [2]