chef and churu

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>

typedef long long ll;

using namespace std;

int n,m,q,N,l[100009],r[100009],x[320][100004],nn,a[100009];
ll t[4 * 100009],b[320],csum[100009];

void build(int v,int tl,int tr) {
    if (tl == tr) t[v] = a[tl];
    else {
        int tm = (tl + tr) / 2;
        build(v * 2,tl,tm);
        build(v * 2 + 1,tm + 1,tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}
void upd(int v,int tl,int tr,int pos,int val) {
    if (tl == tr) t[v] = val;
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            upd(v * 2,tl,tm,pos,val);
        else
            upd(v * 2 + 1,tm + 1,tr,pos,val);

        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}
ll getsum(int v,int tl,int tr,int L,int R) {
    if (L > tr || tl > R) return 0;
    if (L <= tl && tr <= R) return t[v];
    int tm = (tl + tr) / 2;
    return getsum(v * 2,tl,tm,L,R) + getsum(v * 2 + 1,tm + 1,tr,L,R);
}

ll get(int L,int R) {
    ll ret = 0;
    for (int i = L; i <= R;) {

        if ( i % N == 0  && i + N - 1 <= R ) {
            ret += b[i/N];
            i += N;
            //printf("%d %I64d\n",i,ret);
            continue;
        }
        else ret += getsum(1,1,n,l[i],r[i]),i++;

        //printf("%d %I64d\n",i,ret);
    }
    return ret;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int q,L,R;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        csum[i] = csum[i-1] + a[i];
    }
    build(1,1,n);

    N = (int)sqrt(n + .0);
    for (int i = 1; i <= n; i++ ) {
        cin>> l[i] >> r[i];
        //l[i]--; r[i]--;
        b[i / N] += csum[r[i]] - csum[l[i]-1];
        x[i / N][l[i]]++;
        x[i / N][r[i]+1]--;
    }
    for (int i = 0; i <= n / N; i++)
        for (int j = 1; j <= n; j++)
            x[i][j] += x[i][j-1];

    cin >> m;
    while(m--) {
        scanf("%d%d%d",&q,&L,&R);
        if (q == 1) {
            upd(1,1,n,L,R);

            for (int i = 0; i <= n / N; i++)
                b[i] += x[i][L] * (R - a[L]);
            a[L] = R;
        }
        else printf("%I64d\n",get(L,R));
    }
}