Square root decomposition

sqrtDecomp.cpp

// https://cses.fi/problemset/task/1648

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class SQRT {
   private:
    vector<ll> blocks, arr;
    ll n;

    ll queryR(ll r) {
        if (r == -1) {
            return 0;
        }
        ll res = 0;
        for (ll i = 0; i < r / n; i++) {
            res += blocks[i];
        }
        for (ll i = (r / n) * n; i <= r; i++) {
            res += arr[i];
        }
        return res;
    }

   public:
    SQRT(vector<ll> &a) {
        n = ceil(sqrt(a.size()));
        arr = a;
        blocks = vector<ll>(n);
        for (ll i = 0; i < a.size(); i++) {
            blocks[i / n] += a[i];
        }
    }

    void update(ll i, ll value) {
        blocks[i / n] += value - arr[i];
        arr[i] = value;
    }

    ll query(ll l, ll r) {
        return queryR(r) - queryR(l - 1);
    }
};

int main() {
    ll n, q;
    cin >> n >> q;

    vector<ll> a(n);
    for (ll &i : a) {
        cin >> i;
    }

    SQRT sq(a);

    while (q--) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll k, u;
            cin >> k >> u;
            sq.update(--k, u);
        } else {
            ll a, b;
            cin >> a >> b;
            cout << sq.query(--a, --b) << '\n';
        }
    }
}