线段树：从零开始理解这个“万能”数据结构

线段树，说实话，是我在数据结构里最常用的工具之一。它不像链表那样基础，也不像红黑树那样复杂到让人头疼。它就是一个——嗯，怎么形容呢——一个专门处理区间问题的“瑞士军刀”。

我记得刚学线段树那会儿，总觉得它很神秘。后来在项目中处理一个实时股票数据的区间统计，才真正体会到它的威力。今天我就带你从最基础的概念开始，一步步把线段树吃透。

线段树是什么？

说白了，线段树就是一棵二叉树。每个节点代表一个区间。根节点是整个数组，叶子节点是单个元素。

你想想看，如果我们要查一个数组里某段区间的最大值，最笨的办法就是遍历。但数据量一大，比如几十万条，那就慢得没法用了。线段树就是来解决这个问题的——它能在 O(log n) 的时间里完成区间查询和更新。

线段树的结构长什么样？

假设我们有一个数组 arr = [1, 3, 5, 7, 9, 11]。线段树的结构是这样的：

看到没？每个节点存的是区间和。根节点 [0,5] 存的是整个数组的和 36。左孩子 [0,2] 存前三个数的和 9，右孩子 [3,5] 存后三个数的和 27。这样一层层分下去，直到叶子节点。

建树：把数组变成线段树

建树的过程，其实就是递归。我习惯用数组来存线段树，因为完全二叉树可以用数组完美表示。父节点下标是 i，左孩子就是 2*i，右孩子是 2*i+1。

#define MAXN 100005
int tree[MAXN * 4];  // 线段树数组，一般开4倍空间

void build(int node, int start, int end, int arr[]) {
    if (start == end) {
        // 叶子节点，直接赋值
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    int left = node * 2;
    int right = node * 2 + 1;
    
    build(left, start, mid, arr);
    build(right, mid + 1, end, arr);
    
    // 回溯时合并左右孩子的信息
    tree[node] = tree[left] + tree[right];  // 区间和
    // tree[node] = max(tree[left], tree[right]);  // 最大值
    // tree[node] = min(tree[left], tree[right]);  // 最小值
}

区间查询：找最大值、最小值、区间和

查询的逻辑其实很直观。我们要查一个区间 [L, R]，就从根节点开始往下走。有三种情况：

• 完全覆盖：当前节点区间完全在 [L, R] 内，直接返回该节点的值。
• 没有交集：当前节点区间和 [L, R] 没关系，返回一个“空值”（比如查和就返回0，查最大值就返回极小值）。
• 部分重叠：继续往下递归，合并左右孩子的结果。

int query_sum(int node, int start, int end, int L, int R) {
    if (R < start || L > end) return 0;  // 没有交集
    if (L <= start && end <= R) return tree[node];  // 完全覆盖
    
    int mid = (start + end) / 2;
    int left = node * 2;
    int right = node * 2 + 1;
    
    int left_sum = query_sum(left, start, mid, L, R);
    int right_sum = query_sum(right, mid + 1, end, L, R);
    return left_sum + right_sum;
}

// 查最大值类似，只是把 + 换成 max
int query_max(int node, int start, int end, int L, int R) {
    if (R < start || L > end) return -2147483648;  // 极小值
    if (L <= start && end <= R) return tree[node];
    
    int mid = (start + end) / 2;
    int left = node * 2;
    int right = node * 2 + 1;
    
    int left_max = query_max(left, start, mid, L, R);
    int right_max = query_max(right, mid + 1, end, L, R);
    return (left_max > right_max) ? left_max : right_max;
}

单点更新：改一个元素的值

单点更新就简单了。找到那个叶子节点，改掉它，然后一路回溯更新父节点。

void update_point(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    int left = node * 2;
    int right = node * 2 + 1;
    
    if (idx <= mid)
        update_point(left, start, mid, idx, val);
    else
        update_point(right, mid + 1, end, idx, val);
    
    tree[node] = tree[left] + tree[right];  // 更新父节点
}

这个操作也是 O(log n)。我在项目中处理股票数据时，每秒可能有上千次更新，线段树完全扛得住。

区间更新与懒标记：真正的重头戏

单点更新好办，但要是给整个区间 [L, R] 里的每个元素都加上一个值呢？一个个更新？那复杂度就是 O(n log n)，还不如直接遍历数组。

这时候就需要懒标记（Lazy Propagation）了。说白了就是：先记着，不急着改。

我举个例子。你要给 [2, 5] 区间每个数加 3。走到某个节点，发现它完全在 [2, 5] 范围内，那就给这个节点打个标记“这里要加 3”，然后直接返回。等下次查询或者更新需要用到这个节点的子节点时，再把标记“下推”下去。

int lazy[MAXN * 4];  // 懒标记数组

void push_down(int node, int start, int end) {
    if (lazy[node] == 0) return;  // 没有标记，直接返回
    
    int left = node * 2;
    int right = node * 2 + 1;
    int mid = (start + end) / 2;
    
    // 把标记传给左右孩子
    lazy[left] += lazy[node];
    lazy[right] += lazy[node];
    
    // 更新左右孩子的值
    tree[left] += lazy[node] * (mid - start + 1);
    tree[right] += lazy[node] * (end - mid);
    
    lazy[node] = 0;  // 清除当前节点的标记
}

void update_range(int node, int start, int end, int L, int R, int val) {
    if (R < start || L > end) return;
    if (L <= start && end <= R) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;  // 打上懒标记
        return;
    }
    
    push_down(node, start, end);  // 下推标记
    int mid = (start + end) / 2;
    int left = node * 2;
    int right = node * 2 + 1;
    
    update_range(left, start, mid, L, R, val);
    update_range(right, mid + 1, end, L, R, val);
    
    tree[node] = tree[left] + tree[right];
}

区间查询（带懒标记版本）

有了懒标记，查询函数也要相应修改。每次进入一个节点，先下推标记，再递归。

int query_range(int node, int start, int end, int L, int R) {
    if (R < start || L > end) return 0;
    if (L <= start && end <= R) return tree[node];
    
    push_down(node, start, end);  // 查询前也要下推
    int mid = (start + end) / 2;
    int left = node * 2;
    int right = node * 2 + 1;
    
    int left_sum = query_range(left, start, mid, L, R);
    int right_sum = query_range(right, mid + 1, end, L, R);
    return left_sum + right_sum;
}

总结一下线段树的核心要点

操作	时间复杂度	关键点
建树	O(n)	递归构建，回溯合并
单点查询	O(log n)	找到叶子节点即可
区间查询	O(log n)	完全覆盖直接返回
单点更新	O(log n)	更新叶子，回溯父节点
区间更新	O(log n)	懒标记是关键

线段树的应用场景其实很多。区间最值、区间和、区间 GCD、甚至区间翻转（用懒标记实现）。我在做算法竞赛的时候，线段树几乎是必考的数据结构。工作中处理日志分析、股票数据、传感器数据，也经常用到。

好了，这一章的内容就到这。代码你多敲几遍，画图理解递归过程，很快就能掌握。