C++线段树实现方法详解（从零开始掌握线段树构建、区间查询与单点更新）

什么是线段树？

线段树（Segment Tree）是一种二叉树结构，用于存储区间信息。每个节点代表一个区间 [l, r]，根节点通常表示整个数组区间 [0, n-1]，而叶子节点则对应数组中的单个元素。通过递归划分区间，线段树可以在 O(log n) 时间内完成区间查询和更新操作。

常见的应用场景包括：

• 区间求和（如：求数组第 2 到第 5 项的和）
• 区间最值（最大值/最小值）
• 支持单点修改或区间修改

线段树的基本结构

我们以“区间求和”为例来实现一个线段树。假设原数组为 arr，长度为 n。线段树通常用数组 tree 来表示（因为是完全二叉树，可用数组模拟）。

为了简化，我们使用 4 * n 的空间来存储线段树（这是安全的上界）。

C++ 线段树实现步骤

1. 定义线段树类或全局变量

#include <iostream>#include <vector>using namespace std;class SegmentTree {private:    vector<long long> tree;  // 线段树数组    vector<long long> arr;   // 原始数组    int n;                   // 数组长度public:    SegmentTree(vector<long long>& nums) {        arr = nums;        n = nums.size();        tree.resize(4 * n);  // 分配足够空间        build(1, 0, n - 1);    }};

2. 构建线段树（build 函数）

从根节点开始，递归地将区间划分为左右子区间，并合并子节点的信息。

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];    }}

3. 区间查询（query 函数）

查询区间 [l, r] 的和。如果当前节点区间完全包含在 [l, r] 中，直接返回；否则递归查询左右子树。

long long 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;    long long left_sum = query(2 * node, start, mid, l, r);    long long right_sum = query(2 * node + 1, mid + 1, end, l, r);    return left_sum + right_sum;}

4. 单点更新（update 函数）

将数组中某个位置的值更新，并同步更新线段树。

void update(int node, int start, int end, int idx, long long 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];    }}

5. 封装公共接口

为了让外部调用更方便，我们可以封装几个公共方法：

// 公共查询接口long long rangeSum(int l, int r) {    return query(1, 0, n - 1, l, r);}// 公共更新接口void updateValue(int idx, long long val) {    update(1, 0, n - 1, idx, val);}

完整示例代码

#include <iostream>#include <vector>using namespace std;class SegmentTree {private:    vector<long long> tree;    vector<long long> arr;    int n;    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];        }    }    long long 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;        long long left_sum = query(2 * node, start, mid, l, r);        long long right_sum = query(2 * node + 1, mid + 1, end, l, r);        return left_sum + right_sum;    }    void update(int node, int start, int end, int idx, long long 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];        }    }public:    SegmentTree(vector<long long>& nums) : arr(nums), n(nums.size()) {        tree.resize(4 * n);        build(1, 0, n - 1);    }    long long rangeSum(int l, int r) {        return query(1, 0, n - 1, l, r);    }    void updateValue(int idx, long long val) {        update(1, 0, n - 1, idx, val);    }};int main() {    vector<long long> nums = {1, 3, 5, 7, 9, 11};    SegmentTree st(nums);    cout << "Sum of [1, 3]: " << st.rangeSum(1, 3) << endl; // 输出 15    st.updateValue(1, 10); // 将索引1的值改为10    cout << "Sum of [1, 3] after update: " << st.rangeSum(1, 3) << endl; // 输出 22    return 0;}

总结

通过本教程，你已经掌握了 C++线段树实现的核心思想和代码编写方法。线段树作为C++数据结构中的重要工具，特别适合处理动态的区间查询与更新问题。虽然初看可能有些复杂，但只要理解了递归构建和分治的思想，就能灵活运用。

建议你动手敲一遍代码，并尝试扩展功能（如支持区间更新、懒标记等）。掌握线段树后，你在算法竞赛或面试中将更具优势！

如果你觉得这篇线段树教程对你有帮助，欢迎收藏并分享给其他学习者！