题解 | #【模板】线段树1#

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;
const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 0x3f3f3f3f;

ll n, q, a[N], tree[N << 2];

inline int lson(int i) {
    return i << 1;
}
inline int rson(int i) {
    return i << 1 | 1;
}

void up(int i) {
    tree[i] = tree[lson(i)] + tree[rson(i)];
}

void build(int i, int pl, int pr) {

    if (pl == pr) {
        tree[i] = a[pl];
        return ;
    }

    int mid = pl + pr >> 1;

    build(lson(i), pl, mid);
    build(rson(i), mid + 1, pr);

    up(i);
}

void updata(int i, int pl, int pr, int pos, int vlu) {
    if (pl == pr && pl == pos) {
        a[pos] += vlu;
        tree[i] += vlu;//更新树
        return ;
    }

    int mid = pl + pr >> 1;

    if (pos <= mid) {
        updata(lson(i), pl, mid, pos, vlu);
    } else {
        updata(rson(i), mid + 1, pr, pos, vlu);
    }

    up(i);
}

ll query(int i, int pl, int pr, int L, int R) {
    if (L <= pl && pr <= R) {
        return tree[i];
    }

    int mid = pl + pr >> 1;

    ll res = 0;

    if (L <= mid) {
        res += query(lson(i), pl, mid, L, R);
    }
    if (R > mid) {
        res += query(rson(i), mid + 1, pr, L, R);
    }

    return res;
}

void solve() {
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            updata(1, 1, n, l, r);
        } else {
            cout << query(1, 1, n, l, r) << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}