模板_SEG_TREE

#include<bits/stdc++.h>

#define maxn 500005

#define int long long

using namespace std;

inline int read()

{

    char x = getchar();

    int lin = , f = ;

    while(x < '' || x > '')

    {

        if(x == '-') f = -;

        x = getchar();

    }

    while(x >= '' && x <= '')

    {

        lin = (lin << ) + (lin << ) + x - '';

        x = getchar();

    }

    return lin * f;

}

#define PII pair<int,int>

#define fir first

#define sec second

#define ma(a,b) make_pair(a,b)

#define db double

#define inf 123123123

int n,m,v[maxn],x,y,ty,val;

struct tree{

    int l,r,add,val;

}tr[maxn];

#define le tr[k].l

#define re tr[k].r

#define upd tr[k].val = tr[k << 1].val + tr[k << 1 | 1].val;

void pbd(int k,int val)

{

    tr[k].val = tr[k].val + (re - le + ) * val;

    tr[k].add = tr[k].add + val;

}

void pb(int k)

{

    if(tr[k].add)

    {

        pbd(k << ,tr[k].add);

        pbd(k <<  | ,tr[k].add);

        tr[k].add = ;

    }

}

void update(int l,int r,int k,int val)

{

    if(l <= le && re <= r) { pbd(k,val); return; }

    pb(k);

    int mid = le + re >> ;

    if(l <= mid) update(l,r,k << ,val);

    if(r > mid) update(l,r,k <<  | ,val);

    upd;

}

int query(int l,int r,int k)

{

    if(l <= le && re <= r) return tr[k].val;

    pb(k);

    int ans = ,mid = le + re >> ;

    if(l <= mid) ans = ans + query(l,r,k << );

    if(r > mid) ans = ans + query(l,r,k <<  | );

    return ans;

}

void build(int l,int r,int k)

{

    le = l; re = r;

    if(l == r) { tr[k].val = v[l]; return; }

    int mid = l + r >> ;

    build(l,mid,k << ); build(mid + ,r,k <<  | );

    upd;

}

signed main(){

    n = read(); m = read();

    for(int i = ; i <= n; i++) v[i] = read();

    build(,n,);

    for(int i = ; i <= m; i++)

    {

        ty = read(); x = read(); y = read();

        if(ty == ) { val = read(); update(x,y,,val); }

        else printf("%lld\n",query(x,y,));

    }

}