题目大意：

两个操作

1 id op  把id的位置+op

2 id op  查询在【id。op】之间的全部的数的差

思路：

关键是pushup函数。

自己退一下会发现。跟区间的总和，区间的节点个数有关。

比方假设左区间是 1 2 的话

右区间来一个 9

那么

就要加上

9-1+9-2

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <set>

#define inf 0x3f3f3f3f

#define maxn 222222

#define keyTree (ch[ch[root][1]][0])

//当把l-1放在根节点  r+1放在根节点的右子树

//那么根节点的右子树的左子树就是[l,r] 这个区间的全部值

using namespace std;

typedef long long LL;

int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn];

int root,top1,top2;

LL ans[maxn],val[maxn],a[maxn],b[maxn];

LL sum[maxn];

set <LL> tab;

void Treaval(int x)

{

    if(x)

    {

        Treaval(ch[x][0]);

        printf("%I64d ",val[x]);

        Treaval(ch[x][1]);

    }

}

void debug()

{

   // printf("root=%d\n",root);

    Treaval(root);

    puts("");

}

void New(int &x,int PRE,LL v)

{

    if(top2)x=S[--top2];

    else x=++top1;

    ch[x][0]=ch[x][1]=0;

    siz[x]=1;

    pre[x]=PRE;

    /*special*/

    sum[x]=v;

    ans[x]=0;

    val[x]=v;

}

void pushup(int x)/*special*/

{

    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;

    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];

    ans[x]=ans[ch[x][0]]+ans[ch[x][1]]+siz[ch[x][0]]*val[x]-sum[ch[x][0]]+sum[ch[x][1]]-val[x]*siz[ch[x][1]]+siz[ch[x][0]]*sum[ch[x][1]]-siz[ch[x][1]]*sum[ch[x][0]];

}

void pushdown(int x)/*special*/

{

}

void build(int &x,int s,int e,int f)

{

    if(s>e)return;

    int mid=(s+e)>>1;

    New(x,f,a[mid]);

    if(s<mid)build(ch[x][0],s,mid-1,x);

    if(e>mid)build(ch[x][1],mid+1,e,x);

    pushup(x);

}

void Rotate(int x,int kind)

{

    int y=pre[x];

    pushdown(x);

    pushdown(y);

    ch[y][!kind]=ch[x][kind];

    pre[ch[x][kind]]=y;

    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;

    pre[x]=pre[y];

    ch[x][kind]=y;

    pre[y]=x;

    pushup(y);

}

void Splay(int x,int goal)

{

    pushdown(x);

    while(pre[x]!=goal)

    {

        if(pre[pre[x]]==goal)

        Rotate(x,ch[pre[x]][0]==x);

        else

        {

            int y=pre[x];

            int kind=ch[pre[y]][0]==y;

            if(ch[y][kind]==x){

                Rotate(x,!kind);

                Rotate(x,kind);

            }

            else {

                Rotate(y,kind);

                Rotate(x,kind);

            }

        }

    }

    pushup(x);

    if(goal==0)root=x;

}

void RotateTo(int k,int goal)

{

    int r=root;

    pushdown(r);

    while(siz[ch[r][0]]!=k)

    {

        if(k<siz[ch[r][0]])

        {

            r=ch[r][0];

        }

        else

        {

            k-=siz[ch[r][0]]+1;

            r=ch[r][1];

        }

        pushdown(r);

    }

    Splay(r,goal);

}

void erase(int x)

{

    int y=pre[x];

    int head=0,tail=0;

    for(que[tail++]=x;head<tail;head++)

    {

        S[top2++]=que[head];

        if(ch[que[head]][0])que[tail++]=ch[que[head]][0];

        if(ch[que[head]][1])que[tail++]=ch[que[head]][1];

    }

    ch[y][ch[y][1]==x]=0;

    pushup(y);

}

void init(int n)

{

    root=top1=top2=0;

    ch[0][0]=ch[0][1]=siz[0]=pre[0]=0;

    ans[0]=sum[0]=val[0]=0;

    New(root,0,-inf);

    New(ch[root][1],root,inf);

    siz[root]=2;

    for(int i=0;i<n;i++)

    {

        scanf("%I64d",&a[i]);

        tab.insert(a[i]);

        b[i]=a[i];

    }

    tab.insert(-inf);tab.insert(inf);

    sort(a,a+n);

    build(keyTree,0,n-1,ch[root][1]);

    pushup(ch[root][1]);

    pushup(root);

}

int find(LL x,int t)

{

    if(x==val[t])return t;

    else if(x>val[t])return find(x,ch[t][1]);

    else return find(x,ch[t][0]);

}

set<LL>::iterator it;

int add(int x,LL Num,int pos)

{

    if(Num<=val[x])

    {

        if(ch[x][0]==0)

        {

            Splay(x,0);

            int S=siz[ch[root][0]];

            RotateTo(S-1,0);

            RotateTo(S,root);

            New(keyTree,ch[root][1],Num);

            pushup(ch[root][1]);

            pushup(root);

        }

        else add(ch[x][0],Num,pos);

    }

    else

    {

        if(ch[x][1]==0)

        {

            Splay(x,0);

            int S=siz[ch[root][0]];

            RotateTo(S,0);

            RotateTo(S+1,root);

            New(keyTree,ch[root][1],Num);

            pushup(ch[root][1]);

            pushup(root);

        }

        else add(ch[x][1],Num,siz[ch[x][0]]+1+pos);

    }

}

int main()

{

    tab.clear();

    int n;

    scanf("%d",&n);

    init(n);

    //debug();

    int m;

    scanf("%d",&m);

    while(m--)

    {

        int op;

        int l,r;

        scanf("%d%d%d",&op,&l,&r);

        if(op==1)

        {

            it=tab.lower_bound(b[l-1]);

            //printf("*it = %I64d\n",*it);

            int pos=find(*it,root);

            //printf("---%I64d\n",val[pos]);

            Splay(pos,0);

            int Spos=siz[ch[root][0]];

            RotateTo(Spos-1,0);

            RotateTo(Spos+1,root);

            //erase(keyTree);

            erase(keyTree);

            pushup(ch[root][1]);

            pushup(root);

            tab.erase(it);

            b[l-1]+=r;

            tab.insert(b[l-1]);

            add(root,b[l-1],0);

        }

        else

        {

            it=tab.lower_bound(l);

            it--;

            //printf("%I64d\n",*it);

            //printf("%I64d\n",val[]);

            Splay(find(*it,root),0);

            it=tab.upper_bound(r);

            Splay(find(*it,root),root);

            printf("%I64d\n",ans[keyTree]);

        }

        //debug();

    }

    return 0;

}