用C++实现一个线段树

线段树是一种经典的数据结构，用于解决区间查询问题。下面是一个基本的线段树的实现（以区间求和为例）：

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

const int MAXN = 100010;
int n, m, a[MAXN];

struct SegmentTree {
    int l, r;
    long long sum;
} t[MAXN * 4];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        t[p].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}

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

long long query(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r) return t[p].sum;
    int mid = (t[p].l + t[p].r) >> 1;
    long long res = 0;
    if (l <= mid) res += query(p << 1, l, r);
    if (r > mid) res += query(p << 1 | 1, l, r);
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) update(1, x, y);
        else printf("%lld\n", query(1, x, y));
    }
    return 0;
}

具体实现思路如下：

1. 定义一个结构体 `SegmentTree`，用来存储线段树节点的左右区间边界以及区间和。
2. 定义一个函数 `build`，用来建立线段树。建树的过程是递归的，首先判断当前节点是否为叶子节点，如果是，则将区间和赋值为该节点对应的原数组元素值，否则递归建立左右子树，并将当前节点的区间和计算为左右子树的区间和之和。
3. 定义一个函数 `update`，用来更新线段树中的元素。更新的过程也是递归的，首先判断当前节点是否为要更新的节点，如果是，则将该节点的区间和加上更新值，否则递归更新左右子树，并将当前节点的区间和计算为左右子树的区间和之和。
4. 定义一个函数 `query`，用来查询区间和。查询的过程也是递归的，首先判断当前节点的区间是否被包含在查询区间内，如果是，则直接返回当前节点的区间和，否则递归查询左右子树，并将查询结果相加返回。

以上就是一个简单的线段树的实现，可以用来解决各种区间查询问题。