线段树 [OpenJudge] 平方和

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 500005
#define ll long long

ll add[N<<2];
ll sq[N<<2];
ll sum[N<<2];

void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    sq[rt]=sq[rt<<1]+sq[rt<<1|1];
}
void pushdown(int l,int r,int rt)
{
    if(add[rt])
    {
        int m=(l+r)>>1;
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];

        sq[rt<<1]+=(2*add[rt]*sum[rt<<1]+(m-l+1)*add[rt]*add[rt]);
        sq[rt<<1|1]+=(2*add[rt]*sum[rt<<1|1]+(r-m)*add[rt]*add[rt]);

        sum[rt<<1]+=(m-l+1)*add[rt];
        sum[rt<<1|1]+=(r-m)*add[rt];
        add[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    add[rt]=0;
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        sq[rt]=sum[rt]*sum[rt];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c)
{
    if(l==L && r==R)
    {
        add[rt]+=c;
        sq[rt]+=2*sum[rt]*c+(r-l+1)*c*c;
        sum[rt]+=(r-l+1)*c;
        return;
    }
    int m=(l+r)>>1;
    pushdown(l,r,rt);
    if(R<=m) update(l,m,rt<<1,L,R,c);
    else if(L>m) update(m+1,r,rt<<1|1,L,R,c);
    else
    {
        update(l,m,rt<<1,L,m,c);
        update(m+1,r,rt<<1|1,m+1,R,c);
    }
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R)
{
    if(l==L && r==R)
    {
        return sq[rt];
    }
    int m=(l+r)>>1;
    pushdown(l,r,rt);
    if(R<=m) return query(l,m,rt<<1,L,R);
    else if(L>m) return query(m+1,r,rt<<1|1,L,R);
    else return query(l,m,rt<<1,L,m)+query(m+1,r,rt<<1|1,m+1,R);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        while(m--)
        {
            int op,a,b,c;
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d%d",&a,&b,&c);
                update(1,n,1,a,b,c);
            }
            else
            {
                scanf("%d%d",&a,&b);
                printf("%lld\n",query(1,n,1,a,b));
            }
        }
    }
    return 0;
}