线段树

线段树（Segment Tree）是一种二叉树数据结构，主要用于高效处理区间查询和更新操作。它常用于解决涉及数组区间的问题，如区间求和、区间最小值/最大值、区间更新等。

核心思想

线段树将数组划分为多个区间，每个节点代表一个区间，叶子节点代表单个元素，非叶子节点代表其子节点区间的合并。通过这种结构，线段树可以在对数时间内完成区间查询和更新。

主要操作

1. 构建（Build）：

   • 递归地将数组划分为子区间，直到每个区间只包含一个元素。
   • 每个节点存储其代表区间的信息（如和、最小值等）。

2. 查询（Query）：

   • 给定一个区间 [L, R]，递归地查询与 [L, R] 有交集的节点。
   • 合并查询结果，返回所需信息。

3. 更新（Update）：

   • 更新某个元素的值，递归地更新包含该元素的所有区间节点。
   • 确保所有相关节点的信息同步更新。

示例

假设有一个数组 [1, 3, 5, 7, 9, 11]，构建线段树后：

• 根节点代表整个数组 [0, 5]。
• 左子节点代表 [0, 2]，右子节点代表 [3, 5]。
• 叶子节点分别代表单个元素 [0], [1], [2], [3], [4], [5]。

代码示例（Python）

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 2 ** (self.n - 1).bit_length()
        self.tree = [0] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, l, r):
        l += self.size
        r += self.size
        res = 0
        while l <= r:
            if l % 2 == 1:
                res += self.tree[l]
                l += 1
            if r % 2 == 0:
                res += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return res

    def update(self, idx, value):
        idx += self.size
        self.tree[idx] = value
        idx //= 2
        while idx >= 1:
            self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]
            idx //= 2

# 使用示例
data = [1, 3, 5, 7, 9, 11]
st = SegmentTree(data)
print(st.query(1, 4))  # 输出 24 (3 + 5 + 7 + 9)
st.update(2, 10)
print(st.query(1, 4))  # 输出 29 (3 + 10 + 7 + 9)

总结

线段树通过将数组划分为多个区间，并在每个节点存储区间信息，实现了高效的区间查询和更新操作。它在处理区间相关问题时非常有用，尤其适合需要频繁查询和更新的场景。

---

以下是使用C++实现的线段树示例代码，支持区间求和、单点更新和区间查询操作：

C++ 线段树示例代码

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class SegmentTree {
private:
    vector<int> tree; // 线段树数组
    int n; // 原始数组的大小

    // 构建线段树
    void build(const vector<int>& data, int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start]; // 叶子节点，存储单个元素
        } else {
            int mid = (start + end) / 2;
            build(data, 2 * node + 1, start, mid); // 递归构建左子树
            build(data, 2 * node + 2, mid + 1, end); // 递归构建右子树
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 合并左右子树的值
        }
    }

    // 区间查询
    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return 0; // 区间无交集，返回0
        }
        if (l <= start && r >= end) {
            return tree[node]; // 当前区间完全包含在查询区间内
        }
        int mid = (start + end) / 2;
        int leftSum = query(2 * node + 1, start, mid, l, r); // 查询左子树
        int rightSum = query(2 * node + 2, mid + 1, end, l, r); // 查询右子树
        return leftSum + rightSum; // 合并左右子树的结果
    }

    // 单点更新
    void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            tree[node] = value; // 找到目标叶子节点，更新值
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, value); // 递归更新左子树
            } else {
                update(2 * node + 2, mid + 1, end, idx, value); // 递归更新右子树
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; // 更新父节点的值
        }
    }

public:
    SegmentTree(const vector<int>& data) {
        n = data.size();
        int height = (int)ceil(log2(n)); // 计算树的高度
        int maxSize = 2 * (int)pow(2, height) - 1; // 线段树的最大大小
        tree.resize(maxSize, 0); // 初始化线段树数组
        build(data, 0, 0, n - 1); // 构建线段树
    }

    // 区间查询接口
    int queryRange(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    // 单点更新接口
    void updatePoint(int idx, int value) {
        update(0, 0, n - 1, idx, value);
    }
};

int main() {
    vector<int> data = {1, 3, 5, 7, 9, 11};
    SegmentTree st(data);

    // 查询区间 [1, 4] 的和
    cout << "Sum of range [1, 4]: " << st.queryRange(1, 4) << endl; // 输出 24 (3 + 5 + 7 + 9)

    // 更新索引 2 的值为 10
    st.updatePoint(2, 10);

    // 再次查询区间 [1, 4] 的和
    cout << "Sum of range [1, 4] after update: " << st.queryRange(1, 4) << endl; // 输出 29 (3 + 10 + 7 + 9)

    return 0;
}

---

代码说明

1. 线段树结构：

   • 使用数组 tree 存储线段树节点。
   • 每个节点存储一个区间的信息（如区间和）。

2. **构建函数 (build)**：

   • 递归地将原始数组划分为子区间，构建线段树。

3. **查询函数 (query)**：

   • 递归地查询与目标区间 [l, r] 有交集的节点，并返回区间和。

4. **更新函数 (update)**：

   • 递归地更新目标叶子节点，并同步更新其父节点的值。

5. 接口函数：

   • queryRange(l, r)：查询区间 [l, r] 的和。
   • updatePoint(idx, value)：更新索引 idx 处的值为 value。

---

示例输出

Sum of range [1, 4]: 24
Sum of range [1, 4] after update: 29

---

总结

这个C++实现的线段树支持区间求和、单点更新和区间查询操作，适用于需要高效处理区间问题的场景。通过递归构建和查询，线段树能够在 (O(\log n)) 时间内完成操作。