SQRT Decomposotion

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

int n, k;
vector<int> a, b, add;

void update(int l, int r, int x) {
    int bl = l / k, br = r / k;
    if (bl != br) {
        for (int i = l; i < (bl + 1) * k; i++) {
            a[i] += x;
            b[bl] += x;
        }
        for (int i = br * k; i <= r; ++i) {
            a[i] += x;
            b[br] += x;
        }
        for (int i = bl + 1; i < br; ++i) {
            b[i] += k * x;
            add[i] += x;
        }
    } else {
        for (int i = l; i <= r; ++i) {
            a[i] += x;
            b[i / k] += x;
        }
    }
}

int sum(int l, int r) {
    int bl = l / k, br = r / k;

    int res = 0;

    if (bl != br) {
        for (int i = l; i < (bl + 1) * k; ++i) {
            res += a[i] + add[i / k];
        }
        for (int i = br * k; i <= r; ++i) {
            res += a[i] + add[i / k];
        }
        for (int i = bl + 1; i < br; ++i) {
            res += b[i];
        }
    } else {
        for (int i = l; i <= r; ++i) {
            res += a[i] + add[i / k];
        }
    }

    return res;
}

int main() {
    cin >> n;
    a.resize(n);
    k = int(sqrt(n) + 0.99);
    b.resize(k + 1, 0);
    add.resize(k + 1, 0);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i / k] += a[i];
    }


    int q;
    cin >> q;

    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        l--; r--;
        if (op == 1) {
            int x;
            cin >> x;
            update(l, r, x);
        } else {
            cout << sum(l, r) << endl;
        }
    }

    return 0;
}