线段树 – cormidの小破站

一、引言：区间查询与修改的性能瓶颈

在算法设计中，处理数组的区间操作是一类经典问题。假设存在一个长度为 N 的数组，需要频繁执行以下两种操作：

区间查询：计算数组中 [L, R] 区间的元素之和（或最大值、最小值等）。
动态修改：更新数组中某个元素的值，或将 [L, R] 区间内的所有元素统一增加指定数值。

若采用常规的数据结构，性能存在明显瓶颈：

采用普通数组：单点修改的时间复杂度为 O(1)，但区间查询需要遍历整个区间，时间复杂度为 O(N)。
采用前缀和数组：区间查询的时间复杂度优化至 O(1)，但每次修改单点元素后，需要重构后续所有的前缀和，修改的时间复杂度劣化为 O(N)。

当上述操作交替进行 M 次时，总体时间复杂度将达到 O(M × N)。在数据规模（N 和 M）达到 10^5 级别时，必然会导致运行超时。为了打破这一瓶颈，引入线段树（Segment Tree）可以将“区间查询”与“动态修改”的时间复杂度同时优化至 O(log N)。

二、线段树的核心思想与存储结构

线段树的本质是一种基于分治思想的二叉树。树中的每个节点并不表示原数组中的单个元素，而是维护一段连续区间的统计信息（如区间和、区间最值等）。

1. 结构拆解

以一个长度为 8 的数组为例，线段树的区间划分逻辑如下：

根节点：维护整个数组区间 [1, 8] 的信息。
左右子树：根节点将区间等分为两部分，左子节点维护 [1, 4]，右子节点维护 [5, 8]。
叶子节点：区间不断向下二分，直至区间长度为 1（如 [1, 1], [2, 2]），此时叶子节点存储的即为原数组的单点元素信息。

通过这种树形结构，任意一个连续的区间 [L, R] 都可以由树上不超过 O(log N) 个节点所代表的子区间拼接而成。查询时，只需汇总这些关键节点的信息，无需遍历底层元素。

2. 存储方式：一维数组模拟

为了优化内存分配和提高访问速度，线段树通常不采用指针形式的树形结构，而是使用一维数组进行模拟（类似于二叉堆的存储方式）：

假设当前节点的数组下标为 p。
左子节点的下标固定为 2p（在位运算中通常写为 p << 1）。
右子节点的下标固定为 2p + 1（位运算中写为 p << 1 | 1）。

空间分配原则：由于最底层的叶子节点在数组映射中可能会产生空缺，为防止数组越界，线段树的数组容量必须开辟为原数组长度的 4 倍（即 4 * MAXN）。

三、线段树的基础操作

以维护“区间和”为例，线段树的构建与查询依赖以下核心逻辑。

1. 向上更新 (PushUp)

当子节点的信息发生变动时，需要将其状态传递并汇总至父节点。

C++

void pushUp(int p) {
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}

2. 递归建树 (Build)

从根节点出发，递归划分区间直至叶子节点。在叶子节点完成赋初值后，自底向上调用 PushUp 汇总信息。

C++

void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushUp(p);
}

3. 区间查询 (Query)

查询目标区间 [L, R] 的统计结果。若当前节点所维护的区间 [l, r] 被目标区间完全覆盖，则直接返回该节点的值；否则，将查询指令下发至存在交集的子节点。

C++

long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[p];
    }
    int mid = (l + r) >> 1;
    long long sum = 0;
    if (L <= mid) sum += query(p << 1, l, mid, L, R);
    if (R > mid) sum += query(p << 1 | 1, mid + 1, r, L, R);
    return sum;
}

四、性能优化的关键：懒标记（Lazy Tag）机制

基础的线段树在处理“单点修改”时效率极高，但如果需要进行“区间修改”（例如对区间 [1, 1000] 内的所有元素增加一个固定值），逐个修改底层叶子节点会使时间复杂度退化至 O(N)。

为了解决这一问题，引入了**懒标记（Lazy Tag）**机制。

其核心逻辑为：当进行区间修改时，若当前节点维护的区间 [l, r] 被修改区间 [L, R] 完全覆盖，则直接更新当前节点的值，并在此节点上记录一个“标记”（Tag），表示“该节点的所有子孙节点都需要进行相应的修改”。此时立即终止向下递归。只有当后续的查询或修改操作必须访问该节点的子节点时，才将这个标记向下传递（PushDown）。

向下传递 (PushDown) 的实现：

C++

void pushDown(int p, int l, int r) {
    if (lazy[p]) {
        int mid = (l + r) >> 1;
        // 传递标记至左子节点并更新值
        lazy[p << 1] += lazy[p];
        tree[p << 1] += lazy[p] * (mid - l + 1); 
        
        // 传递标记至右子节点并更新值
        lazy[p << 1 | 1] += lazy[p];
        tree[p << 1 | 1] += lazy[p] * (r - mid); 
        
        // 清空当前节点的标记
        lazy[p] = 0;
    }
}

五、完整 C++ 模板实现

以下为包含懒标记机制、支持区间修改与区间和查询的线段树完整 C++ 代码：

C++

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 5;
long long arr[MAXN];
long long tree[MAXN << 2]; 
long long lazy[MAXN << 2]; 

void pushUp(int p) {
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}

void pushDown(int p, int l, int r) {
    if (lazy[p]) {
        int mid = (l + r) >> 1;
        lazy[p << 1] += lazy[p];
        tree[p << 1] += lazy[p] * (mid - l + 1);
        
        lazy[p << 1 | 1] += lazy[p];
        tree[p << 1 | 1] += lazy[p] * (r - mid);
        
        lazy[p] = 0; 
    }
}

void build(int p, int l, int r) {
    lazy[p] = 0;
    if (l == r) {
        tree[p] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushUp(p);
}

void update(int p, int l, int r, int L, int R, long long val) {
    if (L <= l && r <= R) {
        tree[p] += val * (r - l + 1);
        lazy[p] += val;
        return;
    }
    pushDown(p, l, r);
    
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, val);
    if (R > mid) update(p << 1 | 1, mid + 1, r, L, R, val);
    
    pushUp(p);
}

long long query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tree[p];
    }
    pushDown(p, l, r);
    
    int mid = (l + r) >> 1;
    long long sum = 0;
    if (L <= mid) sum += query(p << 1, l, mid, L, R);
    if (R > mid) sum += query(p << 1 | 1, mid + 1, r, L, R);
    
    return sum;
}

int main() {
    int n = 5;
    for (int i = 1; i <= n; i++) arr[i] = i; 
    
    build(1, 1, n); 
    cout << "区间 [2, 4] 的初始和: " << query(1, 1, n, 2, 4) << "\n";
    
    update(1, 1, n, 2, 4, 2);
    cout << "区间 [2, 4] 修改后的和: " << query(1, 1, n, 2, 4) << "\n";
    
    return 0;
}