Segment Tree

/*
======================
[     ___T_          ]
[    | 6=6 | =>HI :-)]
[    |__o__|         ]
[ >===]__o[===<      ]
[     [o__]          ]
[      .".           ]
[      |_|           ]
[                    ]
======================
*/

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

struct Tree {
    int size = 1;
    vector<int64_t> sums;
    void init (int n) {
        while (size < n) size *= 2;
        sums.assign(2 * size,0LL);
    }

    void build (vector<int> &a,int x,int lx,int rx) {
        if (rx - lx == 1) {
            if (lx < (int) a.size()) {
                sums[x] = a[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build (a,2 * x + 1,lx,m);
        build (a,2 * x + 2,m,rx);
        sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
    }

    void build (vector<int> &a) {
        build (a,0,0,size);
    }

    void set (int i,int v,int x,int lx,int rx) {
        if (rx - lx == 1) {
            sums[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            set (i,v,2 * x + 1,lx,m);
        } else {
            set (i,v,2 * x + 2,m,rx);
        }
        sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
    }
    void set (int i,int v) {
        set (i,v,0,0,size);
    }
    int64_t sum (int l,int r,int x,int lx,int rx) {
        if (lx >= r or l >= rx) return 0;
        if (lx >= l and rx <= r) return sums[x];
        int m = (lx + rx) / 2;
        int64_t s1 = sum(l,r,2 * x + 1,lx,m);
        int64_t s2 = sum (l,r,2 * x + 2,m,rx);
        return s1 + s2;
    }
    int64_t sum (int l,int r) {
        return sum(l,r,0,0,size);
    }
};

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,m;
         cin >> n >> m;
         Tree st;
         st.init(n);
         vector<int> a(n);
         for (int i = 0; i < n; ++i) {
             cin >> a[i];
         }
         st.build (a);
         for (int i = 1; i <= m; ++i) {
             int type;
             cin >> type;
             if (type == 1) {
                 int idx,v;
                 cin >> idx >> v;
                 st.set(idx,v);
             } else {
                 int l,r;
                 cin >> l >> r;
                 cout << st.sum(l,r) << "\n";
             }
         }
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}