维护平方和

题目：长度为n的数列
两种操作：1为区间所有的数加一个数
2为求区间的平方和

线段树的核心是维护lazy和tree
lazy是存操作（维护操作）
tree是存结果（维护结果）

此题建完树的结果为 a*a+b*b+c*c
操作后的结果  (a+A)*(a+A)+(b+A)*(b+A)+(c+A)*(c+A)
           = (a*a+b*b+c*c) + 3*A*A + 2* (a+b+c) *A
                 ||                         ||
                 \/                         \/
             平方和(未操作前的结果)          和
==> 操后结果=操前结果+len*(操作数)*(操作数)+2*(朴素和)*操作数
所以不仅要维护操后结果(平方和),还要维护朴素和

维护tree
可以比较操前结果和操后结果的异同
再判断要维护几个tree和哪些东西

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n,m;
int a[N];
int ly[N<<2];
struct L{
    int a,b;
}tr[N<<2];
void bulid(int p,int l,int r){
    if(l==r){ tr[p].a=a[l]; tr[p].b=a[l]*a[l];return ; }
    int mid=(l+r) >> 1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tr[p].a = tr[p*2].a + tr[p*2+1].a ;
    tr[p].b =tr[p*2].b + tr[p*2+1].b;    
}
void pushdown(int p,int len){
    tr[p*2].b += 2*tr[p*2].a*ly[p] + (len-len/2)*ly[p]*ly[p];
    tr[p*2].a += ly[p]*(len-len/2);
    tr[p*2+1].b += 2*tr[p*2+1].a*ly[p] + len/2*ly[p]*ly[p];    
    tr[p*2+1].a += ly[p]*len/2;
    ly[p*2] += ly[p]; ly[p*2+1] += ly[p];
    ly[p] = 0;
}
void add(int p,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y){
        tr[p].b += 2*tr[p].a*k + (r-l+1)*k*k;
        tr[p].a +=(r-l+1)*k;
        ly[p]+=k;
        return ;
    }
    pushdown(p,r-l+1);
    int mid=(l+r) >> 1;
    if(x<=mid) add(p*2,l,mid,x,y,k);
    if(y>=mid+1) add(p*2+1,mid+1,r,x,y,k);
    tr[p].a = tr[p*2].a + tr[p*2+1].a ;
    tr[p].b = tr[p*2].b + tr[p*2+1].b ;
}
int ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tr[p].b ;
    }
    pushdown(p,r-l+1);
    int mid = (l+r) >> 1;
    int res=0;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(mid+1<=y) res+=ask(p*2+1,mid+1,r,x,y);
    return res;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    bulid(1,1,n);
    while(m--){
        int op,x,y,k;
        cin >> op >> x >> y;
        if(op==1){
            cin >> k;
            add(1,1,n,x,y,k);
        }
        else cout << ask(1,1,n,x,y) << "\n";
    }
    return 0;
}