C语言线段树详解（从零开始掌握高效区间操作的数据结构）

线段树的基本思想

线段树将整个数组区间 [0, n-1] 不断二分，直到每个叶子节点代表一个元素。每个非叶子节点存储其左右子区间合并后的信息（如和、最大值等）。

例如，对于数组 [1, 3, 5, 7, 9, 11]，其对应的线段树（以区间和为例）如下：

        [0:5] = 36       /          \   [0:2]=9      [3:5]=27   /     \       /      \[0:1]=4 [2]=5 [3:4]=16 [5]=11 /   \         /    \[0]=1 [1]=3  [3]=7 [4]=9

C语言线段树实现步骤

我们将实现一个支持区间求和和单点更新的线段树。以下是完整实现：

1. 定义线段树结构

通常使用数组来模拟二叉树（堆式存储），根节点在索引 1 处（便于计算子节点）。

#include <stdio.h>#include <stdlib.h>#define MAXN 100000  // 原数组最大长度#define TREE_SIZE (4 * MAXN)  // 线段树数组大小（通常开4倍）int arr[MAXN];        // 原始数组long long tree[TREE_SIZE];  // 线段树（存储区间和）

2. 构建线段树（build）

递归构建：若当前节点代表区间 [l, r]，则左子节点为 [l, mid]，右子节点为 [mid+1, r]。

void build(int node, int l, int r) {    if (l == r) {        tree[node] = arr[l];        return;    }    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];}

3. 区间查询（query）

查询区间 [ql, qr] 的和。若当前节点区间完全包含于 [ql, qr]，直接返回；否则递归查询左右子树。

long long query(int node, int l, int r, int ql, int qr) {    if (qr < l || ql > r) {        return 0;  // 无交集    }    if (ql <= l && r <= qr) {        return tree[node];  // 完全包含    }    int mid = (l + r) / 2;    long long left_sum = query(2 * node, l, mid, ql, qr);    long long right_sum = query(2 * node + 1, mid + 1, r, ql, qr);    return left_sum + right_sum;}

4. 单点更新（update）

将位置 idx 的值修改为 val，并更新所有受影响的父节点。

void update(int node, int l, int r, int idx, int val) {    if (l == r) {        arr[idx] = val;        tree[node] = val;        return;    }    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];}

5. 主函数测试

int main() {    int n = 6;    arr[0] = 1; arr[1] = 3; arr[2] = 5;    arr[3] = 7; arr[4] = 9; arr[5] = 11;    build(1, 0, n - 1);    printf("Sum of [1, 4]: %lld\n", query(1, 0, n - 1, 1, 4)); // 输出 24    update(1, 0, n - 1, 2, 10); // 将索引2的值改为10    printf("Sum of [1, 4] after update: %lld\n", query(1, 0, n - 1, 1, 4)); // 输出 29    return 0;}

为什么线段树数组要开4倍？

虽然理论上二叉树高度为 log₂n，但为了确保不会越界（尤其当 n 不是 2 的幂时），通常将线段树数组大小设为原数组的 4 倍。这是经过数学证明的安全上界。

总结

通过本教程，你已经掌握了用 C语言线段树 实现区间求和与单点更新的核心方法。线段树是解决 区间查询与更新 问题的利器，也是学习更高级数据结构（如树状数组、主席树）的基础。建议你动手敲一遍代码，加深理解。

如果你正在准备算法面试或参加编程竞赛，深入掌握 数据结构教程 中的线段树将为你带来巨大优势！

希望这篇 线段树实现 教程对你有帮助。欢迎收藏、分享！