C++ 线段树代码示例：高效解决区间问题

以下是线段树的 C++ 代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int n, m;
int a[MAXN], tree[MAXN << 2];

void build(int l, int r, int i) {
    if (l == r) {
        tree[i] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, i << 1);
    build(mid + 1, r, i << 1 | 1);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

void update(int l, int r, int i, int x, int k) {
    if (l == r) {
        tree[i] += k;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) update(l, mid, i << 1, x, k);
    else update(mid + 1, r, i << 1 | 1, x, k);
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

int query(int l, int r, int i, int ql, int qr) {
    if (ql <= l && qr >= r) return tree[i];
    int mid = (l + r) >> 1, ans = 0;
    if (ql <= mid) ans += query(l, mid, i << 1, ql, qr);
    if (qr > mid) ans += query(mid + 1, r, i << 1 | 1, ql, qr);
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, n, 1);
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) update(1, n, 1, x, y);
        else cout << query(1, n, 1, x, y) << endl;
    }
    return 0;
}

代码功能:

build 函数：构建线段树，将数组 a 中的元素存储到线段树中。
update 函数：更新线段树中指定位置的值。
query 函数：查询线段树中指定区间内的值之和。

使用方法:

输入数组 a 的大小 n 和操作次数 m。
输入数组 a 中的元素。
循环执行 m 次操作，每次操作可以是 update 或 query。

代码示例:

说明:

第一次操作是 update，将下标为 2 的元素值增加 3，更新后的数组 a 为 [1, 5, 3, 4, 5]。
第二次操作是 query，查询下标 1 到 3 的元素之和，结果为 6。
第三次操作是 update，将下标为 3 的元素值减去 2，更新后的数组 a 为 [1, 5, 1, 4, 5]。

线段树是一种高效的数据结构，可以用于解决区间查询和更新问题，在竞赛和实际应用中都有广泛的应用。