数据结构学习：线段树入门

线段树（Segment Tree）是一种非常强大的二叉搜索树，专门用于处理区间（或线段）上的查询和修改操作。它能以 O(log n) 的时间复杂度完成这些操作。

核心思想

线段树的核心思想是将一个大区间递归地分割成两个子区间，直到每个区间只包含一个元素。树的每个节点都代表一个区间。

• 根节点：代表整个区间，例如 [1, n]。
• 非叶子节点：对于代表区间 [L, R] 的节点，它的左子节点代表 [L, M]，右子节点代表 [M+1, R]，其中 M = (L+R)/2。
• 叶子节点：代表只包含一个元素的区间，例如 [i, i]。

节点本身可以存储这个区间的某些信息，例如区间和、最大值、最小值等。

基础实现 (区间求和)

下面是一个基础的线段树实现，用于求解区间和与单点更新。

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;
int arr[MAXN]; // 原始数组
struct Node {
    int sum; // 区间和
} tree[MAXN * 4];

// 建树
void build(int node, int start, int end) {
    if (start == end) {
        tree[node].sum = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(node * 2, start, mid);
    build(node * 2 + 1, mid + 1, end);
    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
}

// 单点更新
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        arr[idx] = val;
        tree[node].sum = val;
        return;
    }
    int mid = (start + end) / 2;
    if (start <= idx && idx <= mid) {
        update(node * 2, start, mid, idx, val);
    } else {
        update(node * 2 + 1, mid + 1, end, idx, val);
    }
    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
}

// 区间查询
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].sum;
    }
    int mid = (start + end) / 2;
    int p1 = query(node * 2, start, mid, l, r);
    int p2 = query(node * 2 + 1, mid + 1, end, l, r);
    return p1 + p2;
}

int main() {
    // 示例
    int n = 5;
    for(int i = 1; i <= n; ++i) arr[i] = i;

    build(1, 1, n);

    cout << "Sum of [1, 3]: " << query(1, 1, n, 1, 3) << endl; // 1+2+3=6
    update(1, 1, n, 2, 5); // a[2] = 5
    cout << "Sum of [1, 3] after update: " << query(1, 1, n, 1, 3) << endl; // 1+5+3=9

    return 0;
}

这只是线段树的冰山一角，它还可以支持更复杂的操作，如区间修改（配合懒惰标记）。