Shared code

#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct range_sum{
    private:
        vector<T> data;
        int n;
        int sz_block;
        vector<T> ps;
        vector<T> b;
    public:
        void init(vector<T> &arr){ // O(n)
            this->data = arr;
            n = arr.size();
            ps.resize(n+1, 0);
            ps[0] = 0;
            for (int i = 1; i <= n; i++) ps[i] = ps[i-1] + arr[i-1];
            sz_block = (int) sqrt (n + 1.0) + 1;
            b.resize(sz_block+1, 0);
            //for(int i = 0 ; i <= n ; i++) cout<<ps[i]<<" ";
            //cout<<'\n';
        }
        T query(int l, int r){ // O(1) - one-based indexing
            //for(int i = 0 ; i <= n ; i++) cout<<ps[i]<<" ";
            //cout<<'\n';
            //cout<<ps[r]<<" "<<b[r/sz_block]<<endl;
            if(l - 1 == 0) return (ps[r] + b[r/sz_block]);
            return (ps[r] + b[r/sz_block]) - (ps[l-1] + b[(l-1)/sz_block]); 
        }
        void update(int l, int val){ // O(sqrt(n)) - one-based indexing
            int prev_val = query(l, l);
            int delta = val - prev_val;
            int st_block = (l / sz_block);
            int en_block = (n / sz_block); // which is equal to sz_block
            if(st_block == en_block){
                for(int i = l; i <= n; i++) ps[i] += delta;
            }else{
                for(int i = l; i < (st_block + 1)*sz_block && i <= n; i++) ps[i] += delta;
                for(int block = st_block + 1; block < en_block; block++) b[block] += delta;
                for(int i = en_block*sz_block; i<=n; i++) ps[i] += delta;
            }
        }
};
int main(int argc, char** argv){
    int n, q;
    cin>>n>>q;
    vector<int64_t> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    range_sum<int64_t> DynamicPrefixSums;
    DynamicPrefixSums.init(a);
    for(int i = 0; i < q; i++){
        int type;cin>>type;
        int a, b;
        cin>>a>>b;
        if(type == 1) DynamicPrefixSums.update(a, b);
        else cout<<DynamicPrefixSums.query(a, b)<<'\n';
    }
}