线段树求条

rt，10pts。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m;
int a[N],tree[N*4],charge[N*4];
void pushdown(int p,int len)
{
    charge[p*2]+=charge[p],charge[p*2+1]+=charge[p];
    tree[p*2]+=(len-len/2)*charge[p],tree[p*2+1]+=len*charge[p];
    charge[p]=0;return;
}
void build(int l=1,int r=n,int p=1)
{
    if(l==r)
    {
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);build(mid+1,r,p*2+1);
    tree[p]=tree[p*2]+tree[p*2+1];return;
}
void update(int l,int r,int k,int cl=1,int cr=n,int p=1)
{
    if(cl>r||cr<l)return;
    if(cl>=l&&cr<=r)
    {
        tree[p]+=k*(cr-cl+1);
        charge[p]+=k;
    }
    else
    {
        int mid=(cl+cr)/2;pushdown(p,cr-cl+1);
        update(l,r,k,cl,mid,p*2);update(l,r,k,mid+1,cr,p*2+1);
        tree[p]=tree[p*2]+tree[p*2+1];
    }
}
int query(int l,int r,int cl=1,int cr=n,int p=1)
{
    if(cl>r||cr<l)return 0;
    if(cl>=l&&cr<=r)return tree[p];
    else
    {
        int mid=(cl+cr)/2;pushdown(p,cr-cl+1);
        return query(l,r,cl,mid,p*2)+query(l,r,mid+1,cr,p*2+1);
    }
}
signed main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build();
    while(m--)
    {
        int op,l,r;scanf("%lld %lld %lld",&op,&l,&r);
        if(op==1)
        {
            int k;scanf("%lld",&k);
            update(l,r,k);
        }
        else printf("%lld\n",query(l,r));
    }
    return 0;
}