C语言线段树详解（从零开始掌握高效区间查询与更新的数据结构）

例如，对于数组 [1, 3, 5, 7, 9, 11]，线段树的根节点保存的是整个区间的和（1+3+5+7+9+11=36），其左子树保存 [0,2] 的和，右子树保存 [3,5] 的和，以此类推。

线段树的基本操作

线段树主要支持两种操作：

• 构建（Build）：根据原始数组构建线段树。
• 查询（Query）：查询某区间的和（或其他聚合信息）。
• 更新（Update）：修改数组中某个位置的值，并同步更新线段树。

C语言实现线段树

下面是一个完整的 C 语言线段树实现，支持区间求和与单点更新：

#include <stdio.h>#include <stdlib.h>#define MAXN 100000  // 假设数组最大长度int arr[MAXN];        // 原始数组int tree[4 * MAXN];   // 线段树数组（通常开4倍空间）// 构建线段树void build(int node, int start, int end) {    if (start == end) {        // 叶子节点        tree[node] = arr[start];    } else {        int mid = (start + end) / 2;        // 递归构建左右子树        build(2 * node, start, mid);        build(2 * node + 1, mid + 1, end);        // 当前节点值 = 左子树 + 右子树        tree[node] = tree[2 * node] + tree[2 * node + 1];    }}// 区间查询 [l, r]int query(int node, int start, int end, int l, int r) {    if (r < start || end < l) {        // 当前区间与查询区间无交集        return 0;    }    if (l <= start && end <= r) {        // 当前区间完全包含在查询区间内        return tree[node];    }    // 否则递归查询左右子树    int mid = (start + end) / 2;    int left_sum = query(2 * node, start, mid, l, r);    int right_sum = query(2 * node + 1, mid + 1, end, l, r);    return left_sum + right_sum;}// 单点更新：将 arr[idx] 改为 valvoid update(int node, int start, int end, int idx, int val) {    if (start == end) {        // 找到叶子节点        arr[idx] = val;        tree[node] = val;    } else {        int mid = (start + end) / 2;        if (idx <= mid) {            // 在左子树中更新            update(2 * node, start, mid, idx, val);        } else {            // 在右子树中更新            update(2 * node + 1, mid + 1, end, idx, val);        }        // 更新当前节点        tree[node] = tree[2 * node] + tree[2 * node + 1];    }}// 示例主函数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("区间 [1, 3] 的和: %d\n", query(1, 0, n - 1, 1, 3));  // 输出 15    update(1, 0, n - 1, 2, 10);  // 将 arr[2] 改为 10    printf("更新后，区间 [1, 3] 的和: %d\n", query(1, 0, n - 1, 1, 3));  // 输出 20    return 0;}

关键点解析

• 数组大小：线段树通常使用数组实现，为避免越界，线段树数组大小一般设为原数组的 4 倍（4 * MAXN）。
• 递归思想：构建、查询、更新都基于分治思想，每次将区间一分为二。
• 时间复杂度：构建 O(n)，查询和更新均为 O(log n)。

应用场景

线段树广泛应用于需要高效区间查询和更新的场景，例如：

• 动态求区间和、最大值、最小值
• 图像处理中的区域统计
• 数据库中的范围索引优化

总结

通过本教程，你已经掌握了如何用 C 语言实现一个基础的线段树。线段树是数据结构教程中的重要内容，也是提升算法能力的关键工具。熟练掌握后，你可以进一步学习懒标记（Lazy Propagation）以支持高效的区间更新操作。

记住，C语言线段树的核心在于理解其递归结构和区间划分逻辑。多写几遍代码，你就能轻松应对各种区间查询问题！