MO's algo

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define ff first
#define ss second
const int mx=200002;

int k,ans[mx],a[mx],sum=0;
struct Query
{
    int index,l,r;
    bool operator<(const Query& other)
    {
        int block_own = l/k;
        int block_other = other.l/k;
        if(block_own == block_other)
            return r < other.r;
        return block_own < block_other;
    }
} query[mx];

void add(int index)
{
    sum+=a[index];
}

void remove(int index)
{
    sum-=a[index];
}

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

    int q;
    cin>>q;
    for(int i=0; i<q; i++)
    {
        cin>>query[i].l>>query[i].r;
        query[i].index = i;
    }
    sort(query,query+q);

    int l=0,r=-1;
    for(int i=0; i<q; i++)
    {
        while(r<query[i].r) add(++r);
        while(l<query[i].l) remove(l++);
        while(r>query[i].r) remove(r--);
        while(l>query[i].l) add(--l);
        ans[query[i].index]=sum;
    }

    for(int i=0; i<q; i++)
        cout<<ans[i]<<"\n";

    return 0;
}