线段树模板

注意：对于一个长度为$ n $ 的区间，需要建立大小为$ 4n $的数组来储存线段树。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500010;
ll a[N];
struct Tree {
    int l, r;
    ll sum;
} tree[N << 2];
int n, m;
int rd() {
    int al = 0, f = 1;
    char b = getchar();
    while (!isdigit(b)) {
        if (b == '-')
            f = -1;
        b = getchar();
    }
    while (isdigit(b)) {
        al = al * 10 + b - '0';
        b = getchar();
    }
    return al * f;
}
inline void build(ll i, ll l, ll r) {
    tree[i].l = l, tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
    return;
}
inline long long search(int i, int l, int r) {
    if (tree[i].l >= l && tree[i].r <= r)
        return tree[i].sum;
    if (tree[i].r < l || tree[i].l > r)
        return 0;
    long long s = 0;
    if (tree[i * 2].r >= l)
        s += search(i * 2, l, r);
    if (tree[i * 2 + 1].l <= r)
        s += search(i * 2 + 1, l, r);
    return s;
}
inline void add(int i, int x, int k) {
    tree[i].sum += k;
    if (tree[i].l == tree[i].r) {
        return;
    }
    if (x <= tree[i * 2].r) {
        add(i * 2, x, k);
    }
    if (tree[i * 2 + 1].l <= x) {
        add(i * 2 + 1, x, k);
    }
}
int main() {
    n = rd(), m = rd();
    build(1, 1, n);
    while (m--) {
        ll p = rd(), x = rd(), k = rd();
        if (p == 1) {
            ll sum = search(1, x, k);
            cout << sum << endl;
        }
        if (p == 0) {
            add(1, x, k);
        }
    }
}