Sqrt-decomposition

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

int main()
{
    int n;
    cin >> n;
    int n_block = sqrt(n)+1;

    vector <int> a(n);
    vector <int> b(n_block);

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

    while (1) {
        int l, r;
        cin >> l >> r;
        int l_block=l/n_block, r_block=r/n_block;
        int s = 0;
        int idx_end=(l_block+1)*n_block-1;
        for (int i=l; i<=idx_end; i++)
            s += a[i];
        for (int i=l_block+1; i<r_block; i++)
            s += b[i];
        for (int i=r_block*n_block; i<=r; i++)
            s += a[i];
        cout << s << endl;
    }

    return 0;
}