Codeforces
CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage

Code

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

class SegmentTree {
  public:
    int n;
    vector<long long> t;
    SegmentTree(int n) {
        this->n = n;
        t.resize(4 * n + 1);
    }

    void build(vector<long long> &a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }

        int tm = (tl + tr) / 2;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm + 1, tr);
        t[v] = t[2 * v] + t[2 * v + 1];
    }

    long long query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (tl == l && tr == r) {
            return t[v];
        }

        int tm = (tl + tr) / 2;
        auto left = query(2 * v, tl, tm, l, min(tm, r));
        auto right = query(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
        return left + right;
    }

    void update(int v, int tl, int tr, int idx, long long new_val) {
        if (tl == tr) {
            t[v] = new_val;
            return;
        }

        int tm = (tl + tr) / 2;
        if (idx <= tm) {
            update(2 * v, tl, tm, idx, new_val);
        } else {
            update(2 * v + 1, tm + 1, tr, idx, new_val);
        }

        t[v] = t[2 * v] + t[2 * v + 1];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

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

    SegmentTree st(n);
    st.build(a, 1, 0, n - 1);

    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int idx;
            long long new_val;
            cin >> idx >> new_val;
            idx--;

            st.update(1, 0, n - 1, idx, new_val);
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            r--;

            cout << st.query(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}