进阶版树状数组

tree[1]+tree[2]+……tree[i]=a[i]

 a[1]+a[2]+……+a[r-1]+a[r]
//用上方公式推导得出
=tree[1]+(tree[1]+tree[2])+……+(tree[1]+……+tree[r])
//根据加法交换律与结合律：
=(tree[1]*(r))+(tree[2]*(r-1))+……(tree[r]*1)
//那么：
=r*(tree[1]+tree[2]+……+tree[r])-(tree[1]*0+tree[2]*1+……+tree[r]*(r-1))

#include<bits/stdc++.h>
#define rg register
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 100005
const double eps=1e-8;
using namespace std;
inline ll read()
{
    char ch=getchar();ll s=0,w=1;
    while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}
    while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
inline void write(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
ll n,m;
ll tree[maxn],tree1[maxn];
inline ll lb(ll x)
{
    return x&-x;
}
inline void add(ll *tree,ll x,ll k)
{
    for(;x<=n;x+=lb(x))
    {
        tree[x]+=k;
    }
}
inline ll query(ll *tree,ll x)
{
    ll ans=0;
    for(;x;x-=lb(x))
    {
        ans+=tree[x];
    }
    return ans;
}
int main()
{
    n=read(),m=read();
    ll now,last=0;
    for( rg ll i=1;i<=n;i++)
    {
        now=read();
        add(tree,i,now-last);
        add(tree1,i,(now-last)*(i-1));
        last=now;
    }
    for(rg ll i=1;i<=m;i++)
    {
        ll x;
        x=read();
        if(x==1)
        {
            ll a,b,c;
            a=read(),b=read();c=read();
            add(tree,a,c);
            add(tree,b+1,-c);
            add(tree1,a,c*(a-1));
            add(tree1,b+1,-c*b);
        }
        else if(x==2)
        {
           ll  a,b;
           a=read(),b=read();
           cout<<b*query(tree,b)-(a-1)*query(tree,a-1)-(query(tree1,b)-query(tree1,a-1))<<endl;
        }
    }
    return 0;
}