参考自http://www.notonlysuccess.com/index.php/segment-tree-complete/

#include
    
     #include
     
      #include
      
       #include
       
        #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn=111111;long long  sum[maxn<<2];long long  col[maxn<<2];void pushUp(int rt){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushDown(int rt,int m){    if(col[rt])    {        col[rt<<1]+=col[rt];        col[rt<<1|1]+=col[rt];        sum[rt<<1]+=col[rt]*(m-(m>>1));        sum[rt<<1|1]+=col[rt]*(m>>1);        col[rt]=0;    }}void build(int l,int r,int rt){    col[rt]=0;    if(r==l)    {        scanf("%lld",&sum[rt]);        return ;    }    int m=(r+l)>>1;    build(lson);    build(rson);    pushUp(rt);}void update(int L,int R,int d,int l,int r,int rt){    if(L<=l&&r<=R)    {        sum[rt]+=d*(r-l+1);        col[rt]+=d;        return;    }    pushDown(rt,r-l+1);    int m=(l+r)>>1;    if(L<=m) update(L,R,d,lson);    if(m
        
         >1;    if(L<=m) ret+=query(L,R,lson);    if(m