深入理解线段树（C++实现与应用详解）

线段树的基本思想

假设我们有一个数组 arr[0...n-1]，线段树会将其构建成一棵完全二叉树：

• 叶子节点存储原数组的元素
• 内部节点存储其子节点所代表区间的聚合信息（如和、最大值等）
• 根节点代表整个区间 [0, n-1]

C++线段树实现步骤

下面我们以区间求和为例，展示如何用C++数据结构实现线段树。

1. 定义线段树类

#include <vector>#include <iostream>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>& input) {        arr = input;        n = arr.size();        tree.resize(4 * n);  // 通常开4倍空间        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);    }};

2. 使用示例

int main() {    vector<long long> arr = {1, 3, 5, 7, 9, 11};        // 创建线段树    SegmentTree st(arr);        // 查询区间 [1, 3] 的和    cout << "Sum of [1, 3]: " << st.rangeSum(1, 3) << endl;  // 输出: 15        // 更新索引 1 的值为 10    st.updateValue(1, 10);        // 再次查询区间 [1, 3] 的和    cout << "Sum of [1, 3] after update: " << st.rangeSum(1, 3) << endl;  // 输出: 22        return 0;}

为什么需要4倍空间？

线段树虽然是二叉树，但为了保证完全二叉树的性质并避免越界，通常将数组大小设为原数组长度的4倍。这是数据结构线段树实现中的一个重要细节。

线段树的应用场景

线段树广泛应用于各种需要高效区间操作的场景：

• 动态区间求和、求最值
• 区间染色问题
• 区间覆盖统计
• 结合懒标记（Lazy Propagation）处理区间更新

总结

通过本线段树教程，你应该已经掌握了线段树的基本概念、C++实现方法以及使用技巧。线段树是算法竞赛中的利器，也是面试中的高频考点。建议多练习相关题目，加深理解！

记住，掌握C++线段树的关键在于理解其递归构建和查询的过程。动手实现一遍，你会发现它并没有想象中那么复杂！