MO's Algorithm

//Return the sum between the index l and r(both inclusive)  of array.
#include <bits/stdc++.h>
using namespace std;
#define fastIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define endl "\n"

const int N = 1e5 + 5;
int sz;

struct Q
{
    int l, r, idx;
};
Q q[N];
bool cmp(Q a, Q b)
{
    if (a.l / sz == b.l / sz)
    {
        return a.r > b.r;
    }
    else
    {
        return a.l / sz < b.l / sz;
    }
}
void solve()
{

    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sz = sqrt(n);
    int quiries;
    cin >> quiries;
    for (int i = 0; i < quiries; i++)
    {
        int l, r;
        cin >> l >> r;
        q[i].l = l;
        q[i].r = r;
        q[i].idx = i;
    }
    sort(q, q + quiries, cmp);
   
    vector<int> ans(quiries);
    int cur_r = -1, cur_l = 0, l, r;
    int cans = 0;

    for (int i = 0; i < quiries; i++)
    {
        l = q[i].l;
        r = q[i].r;
        l--;
        r--;
        while (cur_r < r)
        {
            cur_r++;
            cans += a[cur_r];
        }
        while (cur_l < l)
        {

            cans -= a[cur_l];
            cur_l++;
        }
        while (cur_l > l)
        {
            cur_l--;
            cans += a[cur_l];
        }
        while (cur_r > r)
        {
            cans -= a[cur_r];
            cur_r--;
        }
        ans[q[i].idx] = cans;
    }
    for (auto it : ans)
        cout << it << endl;
}
int main()
{
    fastIO;
    int t = 1;
    
    while (t--)
    {
        solve();
    }
}