线段树的本质-MuQYY的博客

1. 引言

线段树是一种二叉树形结构的数据结构，用于处理区间查询和区间更新问题。它的核心思想是：将数组递归划分为多个区间（区段），并将这些区间组织成二叉树结构。这种设计使得我们可以在 $O(\log n)$ 时间复杂度内完成区间查询和区间更新操作。

2. 线段树的适用场景

线段树适用于以下场景：

区间查询：在数组的任意区间上执行查询（如求和、最小值、最大值等）。
区间更新：更新数组中某个位置或某个区间内的元素。

相比于普通的前缀和数组或树状数组，线段树支持更灵活的区间操作，如任意区间的最大值、最小值等。

3. 线段树的核心思想

线段树是一棵平衡二叉树，每个节点存储一个区间的信息。如下图所示：

原数组 A： [2, 3, 1, 5, 4, 6, 7, 8]

线段树（求和示意）：
                       [0,7]: 36
                    /               \
            [0,3]: 11              [4,7]: 25
            /      \               /      \
      [0,1]: 5   [2,3]: 6    [4,5]: 10  [6,7]: 15
      /   \      /   \       /   \      /   \
   [0]:2 [1]:3 [2]:1 [3]:5 [4]:4 [5]:6 [6]:7 [7]:8

区间划分的原则

每个节点表示一个数组的区间，例如 [0, 3] 表示数组前四个元素的和。
叶节点：每个叶节点存储的是数组中的单个元素。
非叶节点：存储其左右子节点的区间信息的组合（如区间和、区间最小值）。

性质

完全二叉树：对于一个长度为 $n$ 的数组，线段树的节点数最多为 $4n$。
时间复杂度：查询和更新的时间复杂度为 $O(\log n)$。

4. 线段树的操作

4.1 构建线段树

构建线段树的过程是将数组的每个区间递归划分为更小的子区间，直到每个叶节点存储一个单独的元素。

递归构建的思路：

区间 [l, r] 的中点为 mid = (l + r) / 2。
左子树管理区间 [l, mid]，右子树管理区间 [mid + 1, r]。
每个节点的值是其左右子节点值的组合（如和、最大值）。

代码实现：构建线段树

#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;  // 最大数组长度
int tree[4 * N];        // 线段树数组，大小为 4 * n
int A[N];               // 原数组

// 构建线段树，节点 node 负责区间 [l, r]
void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = A[l];  // 叶节点存储原数组的值
    } else {
        int mid = (l + r) / 2;
        build(2 * node, l, mid);       // 递归构建左子树
        build(2 * node + 1, mid + 1, r);  // 递归构建右子树
        tree[node] = tree[2 * node] + tree[2 * node + 1];  // 区间和
    }
}

4.2 区间查询

区间查询的目的是查询数组某个区间 $[L, R]$ 的和（或最值）。如果查询区间和当前节点的区间完全匹配，就直接返回节点的值；否则，递归查询左右子区间。

代码实现：区间查询

// 查询区间 [L, R] 的和，当前节点 node 负责区间 [l, r]
int query(int node, int l, int r, int L, int R) {
    if (L <= l && r <= R) {  // 完全包含
        return tree[node];
    }
    if (r < L || l > R) {  // 完全不相交
        return 0;
    }
    int mid = (l + r) / 2;
    return query(2 * node, l, mid, L, R) +  // 查询左子区间
           query(2 * node + 1, mid + 1, r, L, R);  // 查询右子区间
}

4.3 单点更新

单点更新的目的是修改数组中的某个元素，并更新线段树中受影响的节点。

代码实现：单点更新

// 将数组 A[idx] 的值更新为 val，当前节点 node 负责区间 [l, r]
void update(int node, int l, int r, int idx, int val) {
    if (l == r) {  // 叶节点
        tree[node] = val;
    } else {
        int mid = (l + r) / 2;
        if (idx <= mid) {
            update(2 * node, l, mid, idx, val);  // 更新左子树
        } else {
            update(2 * node + 1, mid + 1, r, idx, val);  // 更新右子树
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];  // 更新父节点
    }
}