Treap add

#pragma comment(linker, "/STACK:65777216")
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <string>
#include <memory.h>
#include <iterator>
#define y1 trololoy1
#define y0 trololoy0
#define mem(A,X) memset(A,X,sizeof(A))
#define memo(A) memset(A,0,sizeof(A))
#define forn(I,B) for (int I=1;I<=(B);I++)
#define forg(H,V) for (int H=first[V];h;h=next[H])
#define rep(I,B) for (int I=0;I<(B);I++)
#define labs(X) (((X)>0)?(X):(-(X)))
#define ropen(X) freopen(X,"r",stdin)
#define wopen(X) freopen(X,"w",stdout)
#define rwopen(X) freopen(X".in","r",stdin);freopen(X".out","w",stdout)
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(),(X).end()
#define sqr(X) ((X)*(X))

using namespace std;

typedef pair <int,int> pii;
typedef double ld;
typedef long long ll;
typedef pair <ll,ll> pll;
typedef vector<int> vi;
const int N=222222;
const int INF=111111111;
const double eps=1e-9;
const double pi=3.14159265358979;

struct treap{
    int ls,rs,x,y,cost,sum,add,sz;
} t[N];

int c,n,root,a[N],k;

inline int sumof(int v){
    return v?t[v].sum+t[v].add*t[v].sz:0;
}

inline int szof(int v){
    return v?t[v].sz:0;
}

inline void recalc(int v){
    if (!v) return;
    t[v].sum=sumof(t[v].ls)+sumof(t[v].rs)+t[v].cost;
    t[v].sz=szof(t[v].ls)+szof(t[v].rs)+1;
}

inline void push(int v){
    if (!t[v].add) return;
    t[v].cost+=t[v].add;
    t[t[v].ls].add+=t[v].add;
    t[t[v].rs].add+=t[v].add;
    t[v].add=0;
}

void merge(int & x,int l,int r){
    if (!l || !r){
        x=l?l:r;
        return;
    }
    if (t[l].y>t[r].y){
        x=l;
        push(x);
        merge(t[x].rs,t[x].rs,r);
    } else {
        x=r;
        push(x);
        merge(t[x].ls,l,t[x].ls);
    }
    recalc(x);
}

void split(int x,int key,int &l,int &r){
    if (!x){
        l=r=0;
        return;
    }
    push(x);
    if (t[x].x<=key){
        l=x;
        split(t[x].rs,key,t[x].rs,r);
    } else {
        r=x;
        split(t[x].ls,key,l,t[x].ls);
    }
    recalc(x);
}

void insert(int &x){
    if (!x){
        x=c;
        return;
    }
    if (t[c].y>t[x].y){
        split(x,t[c].x,t[c].ls,t[c].rs);
        x=c;
    } else insert(t[c].x<t[x].x?t[x].ls:t[x].rs);
    recalc(x);
}

inline void ins(int key,int cost){
    t[++c]=(treap){0,0,key,a[c],cost,cost,0,1};
    insert(root);
}

void erase(int &x,int key){
    if (!x) return;
    if (t[x].x==key) merge(x,t[x].ls,t[x].rs);
    else erase(t[x].x<key?t[x].rs:t[x].ls,key);
    recalc(x);
}

void print(int x){
    if (!x) return;
    print(t[x].ls);
    cout<<t[x].x<<" ";
    print(t[x].rs);
}

inline int query(int l,int r){
    int L,M1,M2,R;
    split(root,l-1,L,M1);
    split(M1,r,M2,R);
    int q=sumof(M2);
    merge(M1,M2,R);
    merge(root,L,M1);
    return q;
}

inline void add(int l,int r,int x){
    int L,M1,M2,R;
    split(root,l-1,L,M1);
    split(M1,r,M2,R);
    t[M2].add+=x;
    merge(M1,M2,R);
    merge(root,L,M1);
}

int main(){
    ropen("input.txt");
    wopen("output.txt");
    cin>>n;
    forn(i,n) a[i]=i;
    random_shuffle(a+1,a+n+1);
    forn(i,n){
        int x;
        scanf("%d",&x);
        ins(i,x);
    }
    scanf("%d",&n);
    forn(i,n){
        int q,a,b,c;
        scanf("%d%d%d",&q,&a,&b);
        if (!q) scanf("%d",&c);
        if (q) printf("%d\n",query(a,b));
        else add(a,b,c);
    }
}