SegTree

#include <iostream>
#define int long long
using namespace std;

const int N = 2e5 + 5;

int n, q, a[N], t[4 * N];

///O(n)
///we want to calculate value for vertex v which represents the range [vl; vr]
void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = a[vl];
        return;
    }
    int vm = (vl + vr) / 2;
    ///calculate left son
    build(2 * v, vl, vm);
    ///calculate right son
    build(2 * v + 1, vm + 1, vr);

    ///combine them
    t[v] = t[2 * v] + t[2 * v + 1];
}


///O(log n)
void update(int v, int vl, int vr, int pos, int val) {
    if (vl == vr) {
        ///vl == vr == pos
        t[v] = val;
        a[vl] = val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm)
        ///the position in the left half => calculate left son
        update(2 * v, vl, vm, pos, val);
    else
        ///the position in the right half => calculate right son
        update(2 * v + 1, vm + 1, vr, pos, val);

    ///combine them
    t[v] = t[2 * v] + t[2 * v + 1];
}

///O(log n)
int get(int v, int vl, int vr, int l, int r) {
    if (vl == l && vr == r)
        return t[v];
    int vm = (vl + vr) / 2;
    ///completely in the left son
    if (r <= vm)
        return get(2 * v, vl, vm, l, r);

    ///completely in the right son
    if (l > vm)
        return get(2 * v + 1, vm + 1, vr, l, r);

    ///split by vm
    return get(2 * v, vl, vm, l, vm) + get(2 * v + 1, vm + 1, vr, vm + 1, r);
}

signed main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, val;
            cin >> pos >> val;
            update(1, 1, n, pos, val);
        } else {
            int l, r;
            cin >> l >> r;
            cout << get(1, 1, n, l, r) << "\n";
        }
    }

    return 0;
}