线段树基础理论

线段树解决的是动态区间维护问题。它把一个区间递归划分成若干节点，每个节点保存对应区间的摘要，再通过合并这些摘要回答询问。

本文只讨论最基础的下标线段树：坐标范围预先确定，支持单点修改与任意区间查询。区间修改、懒标记、权值线段树和其他扩展在基础结构成立后再分别讨论。

一、问题原型

动态区间和

给定一个长度为 $n$ 的数列 $\{a_i\}$，需要在线处理两类操作：

1. 将某个位置 $a_p$ 修改为 $x$。
2. 查询区间 $[l,r]$ 的元素和。

数据规模：$n,m\le 10^5$。

区间和最自然的静态做法是前缀和，可以在 $O(1)$ 内回答一次查询。但是一次单点修改会影响后面所有前缀，修改又退化为 $O(n)$，所以查询与修改之间存在矛盾。

如果只保存原数组，那么修改很便宜，但查询需要重新遍历区间；如果保存所有前缀，那么查询很便宜，但一次修改又会使大量已经保存的信息失效。

我们希望只保存一组中间尺度的区间信息，使任意查询都能由少量已有区间拼出，同时一次单点修改又只影响少量已有区间。

由此我们引入线段树这个数据结构，它的核心原理是 分治。把整个区间 $[1,n]$ 不断二分，可以让一个位置在每一层只属于一个节点，同时让任意查询区间能够被拆成少量节点区间。

根节点表示整个区间 $[1,n]$。对于任意非叶节点 $[l,r]$，令 $mid=\lfloor(l+r)/2\rfloor$，左儿子表示 $[l,mid]$，右儿子表示 $[mid+1,r]$，叶子节点就是 $l=r$。

由于每次都把区间近似折半，树高为 $O(\log n)$。

同一层的节点区间互不相交，并且恰好覆盖 $[1,n]$，而且每个父节点区间也恰好是左右儿子区间按原顺序拼接后的结果。

这两个性质决定了线段树的基本操作：父节点可以从两个儿子恢复，区间查询也可以被分解成若干个互不相交的节点区间。

示例

例如在 $[1,8]$ 上查询 $[3,7]$，可以把它拆成 $[3,4]$、$[5,6]$ 与 $[7,7]$ 三个节点区间。它们互不重叠，按从左到右合并后恰好得到原询问。

若把位置 $6$ 的值修改掉，只有叶子 $[6,6]$、父区间 $[5,6]$、$[5,8]$ 和根区间 $[1,8]$ 的摘要需要重算。区间分解同时限制了查询与修改实际访问的节点数量。

节点信息 / 区间摘要

接着讨论节点需要存储什么信息。节点内部的元素以后只会通过整个区间参与更大的合并，或者在完整覆盖时直接回答询问，所以只需要保存完成这两件事所需的信息。

对于这样的信息，我们称之为 区间摘要 Info。

区间和

对于区间和来说，摘要只需保存一个 sum，设左右儿子的摘要分别为 $L$ 和 $R$，那么父节点满足 sum = L.sum + R.sum。

更一般的，设运算 $\otimes$ 用来合并两个相邻区间的摘要。若区间 $A$ 在区间 $B$ 左侧，那么它们拼接后的摘要写成 $Info(A \circ B)=Info(A)\otimes Info(B)$。

什么样的信息可以合并？

例如三个连续区间 $A,B,C$ 的摘要，既可能先合并 $A,B$，也可能先合并 $B,C$。

为了让结果与递归划分方式无关，需要满足 $(A\otimes B)\otimes C=A\otimes(B\otimes C)$，也就是合并运算具有结合性。加法、最大值、最小值、异或、按位或和矩阵乘法都满足这一要求。

不过合并不要求交换律。最大子段和、字符串状态和矩阵转移等信息具有方向性，通常是 $A\otimes B\ne B\otimes A$，这时，查询时必须保持原区间的左右顺序。

因此，线段树最核心的代数要求其实是：区间摘要在 merge 下满足结合律，也就是至少形成一个半群。

单位元是什么？

若希望用一个空摘要表示 “这一侧没有查询结果”，还需要单位元 $e$，使得 $e\otimes A=A$ 且 $A\otimes e=A$。区间和的单位元是 $0$，区间最大值可使用负无穷，复杂摘要则要单独设计空状态。

单位元不是线段树建树所必需的，但它能简化区间查询。若单位元难以自然定义，也可以在递归时分别处理只进入左侧、只进入右侧和同时进入两侧三种情况。

如果在结合律之外还存在单位元，那么这套摘要与合并运算就构成一个 幺半群。竞赛中常说 “线段树维护一个幺半群”，数学本质上就是把 Info 与 merge 抽象到了这一层。

二、具体实现

以下三个操作始终围绕同一个不变量：每个节点的 info 都等于它所代表区间的真实摘要。

1. 递归建树

建树时从根区间开始递归。到达叶子 $[i,i]$ 后，由单个元素 $a_i$ 构造摘要；返回父节点时，再按左右顺序合并两个儿子的摘要。

▶

线段树建树

const int maxn = 2e5 + 5;

#define ls ( u << 1 )
#define rs ( u << 1 | 1 )

struct Info {
    ll sum = 0;
};

Info merge( const Info &L, const Info &R ) {
    return { L.sum + R.sum };
}

struct Node {
    int l, r;
    Info info;
} tr[maxn << 2];

void push_up( int u ) {
    tr[u].info = merge( tr[ls].info, tr[rs].info );
}

void build( int u, int l, int r, ll a[] ) {
    tr[u].l = l, tr[u].r = r;
    if( l == r ) {
        tr[u].info = { a[l] };
        return;
    }
    int mid = ( l + r ) >> 1;
    build( ls, l, mid, a );
    build( rs, mid + 1, r, a );
    push_up( u );
}

2. 单点修改

把位置 $p$ 修改为 $x$ 时，从根节点开始判断 $p$ 属于哪个儿子，并只递归进入这一侧。到达叶子后更新摘要，再沿递归路径向上执行 push_up。

注：不包含 $p$ 的节点区间完全没有变化，无需重新计算。包含 $p$ 的节点每层恰好一个，所以修改只影响从叶子到根的一条链。

▶

线段树单点修改

void upd( int u, int pos, ll val ) {
    if( tr[u].l == tr[u].r ) {
        tr[u].info = { val };
        return ;
    }
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( pos <= mid ) upd( ls, pos, val );
    else upd( rs, pos, val );
    push_up( u );
}

3. 区间查询

查询区间 $[l,r]$ 时，若当前节点区间完全包含于询问区间，就直接返回该节点摘要。这个区间已经被完整预处理，没有必要继续访问儿子。

若询问只与一个儿子相交，就递归进入这一侧。若同时跨过中点，就分别查询左右交集，再按左、右顺序合并结果。

▶

线段树区间查询

Info ask( int u, int l, int r ) {
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].info;
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( r <= mid ) return ask( ls, l, r );
    if( mid < l ) return ask( rs, l, r );
    return merge( ask( ls, l, r ), ask( rs, l, r ) );
}

三、复杂度

线段树的叶子数为 $n$，每个非叶节点都有两个儿子，因此有效节点总数小于 $2n$。堆式数组递归实现为了兼容不满二叉树的编号空隙，通常分配约 $4n$ 个节点，空间复杂度仍为 $O(n)$。

建树对每个有效节点只处理一次，所以时间复杂度为 $O(n)$。单点修改只访问一条根到叶子的路径，时间复杂度为 $O(\log n)$。

一次区间查询只有目标区间的左右边界所在路径需要继续分裂，其余完整覆盖部分会立即返回。每层至多产生常数个边界节点，规范分解包含的节点数为 $O(\log n)$，所以单次查询复杂度为 $O(\log n)$。

注：上述结论默认一次 merge 为 $O(1)$。若摘要是 $k\times k$ 矩阵或长度为 $K$ 的 DP 状态，还要乘上一次摘要合并的实际代价。

四、线段树 Vs 树状数组

树状数组采用的是把前缀拆成若干 lowbit 块，所以天然支持前缀查询和单点修改。

若任意区间可以由两个前缀结果通过逆运算消去，通常使用树状数组实现会更省空间，也更省常数。例如区间和满足 $sum(l,r)=pre(r)-pre(l-1)$，所以两种结构都能维护。

不过区间最值没有对应的消去操作，普通树状数组无法从两个前缀最值恢复任意区间最值，而线段树可以直接合并覆盖目标区间的节点。

因此，树状数组的核心是维护前缀，线段树的核心是合并相邻区间。只有前缀结构足够时优先使用树状数组，需要非可消去信息或复杂摘要时再选择线段树，具体参见 树状数组。

五、基础理论的适用边界

本页讨论的是固定坐标的下标线段树，修改只作用于单点。若坐标范围巨大，但实际出现位置稀疏，可以考虑 动态开点；若需要历史版本，可以考虑 可持久化线段树。

若修改作用于区间，当然可以逐点修改，但复杂度会退化。在操作能够直接作用于节点摘要，并且多次操作能够复合时，可以进一步使用 懒标记。

若完整区间的答案可能跨过左右儿子的边界产生，就需要在摘要中额外保存前缀、后缀或其他边界接口，具体参见 线段树信息合并。若节点摘要能够判断某个儿子是否可能包含目标，还可以在线段树上直接下降寻找位置，也就是线段树上二分。

这些扩展没有改变最基础的不变量：每个节点仍然保存自身区间的正确摘要。变化的只是摘要保存什么、修改怎样作用，以及查询怎样利用这些摘要。

六、关联

• 线段树信息合并：从查询要求推导最小充分摘要。
• 浅谈线段树懒标记：研究区间操作怎样作用于摘要，以及待执行操作怎样有序复合。
• 树状数组：维护前缀可消去信息的轻量结构。
• P4513 小白逛公园：具有方向性的跨中点信息合并。
• P4588 数学计算：把时间作为坐标轴，撤销操作转为恢复单位元。

懒标记已经沿操作作用与操作复合形成独立专题，线段树上二分则还是后续候选理论页。基础页只建立它们共同依赖的递归划分、区间摘要与节点不变量。