Square_Root_Decomposition

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, ara[1000], block[1000] = {}, block_size;
    cin >> n;
    block_size = sqrt(n);

    // Input array elements
    for (int i = 0; i < n; i++) {
        cin >> ara[i];
    }

    // Calculate the blocks
    for (int i = 0; i < n; i++) {
        block[i / block_size] += ara[i];
    }

    cout << "block size: " << block_size << endl;

    int q;
    cin >> q;

    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            // Update operation
            ara[x] += y;
            block[x / block_size] += y;
        } else {
            // Query operation (range sum)
            int sum = 0;
            for (int i = x; i <= y; ) {
                if (i % block_size == 0 && i + block_size - 1 <= y) {
                    sum += block[i / block_size];
                    i += block_size;
                } else {
                    sum += ara[i];
                    i++;
                }
            }
            cout << sum << endl;
        }
    }

    return 0;
}