现在写线段树感觉还是蛮不错的
熟能生巧了吗？
感觉自己一直在做模板题
NOS神犇的博客还真是好啊 给了我这么好的学习地方~
线段树把他的每个题吃掉吧
这题要注意的就是...
计算区间大小时（L-R+1）是错的，想当然了；
另外计算的时候记得root<<1的操作；
还有sum+=这个，有些时候要+=有些时候不要
例如在PushUp的时候明显就不要+=了~
#include<iostream>
#define MAXN 100001
using namespace std;__int64 sum[MAXN<<2];
__int64 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]+=(m-(m>>1))*col[rt];sum[rt<<1|1]+=(m>>1)*col[rt];col[rt]=0;}
}void build( int l,int r,int rt )
{col[rt]=0;if( l==r ){ scanf( "%I64d",&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 L,int R,int value,int rt )
{if( l<=L&&R<=r ){col[rt]+=value;sum[rt]+=(__int64)(R-L+1)*value;return ;}PushDown(rt,R-L+1);int m=(L+R)>>1;if( l<=m )update( l,r,L,m,value,rt<<1 );if( r>m )update( l,r,m+1,R,value,rt<<1|1 );PushUp(rt);return ;
}__int64 query( int l,int r,int L,int R,int rt )
{__int64 res=0;if( l<=L&&R<=r )return sum[rt];PushDown(rt,R-L+1);int m=(L+R)>>1;if( l<=m )res+=query( l,r,L,m,rt<<1 );if( r>m )res+=query( l,r,m+1,R,rt<<1|1 );return res;
}int main()
{int n,m;int a,b,v;char c[2];while( scanf( "%d %d",&n,&m )!=EOF ){build( 1,n,1 );while( m-- ){scanf( "\n%s%d%d",&c,&a,&b );if( c[0]=='Q' )printf( "%I64d\n",query(a,b,1,n,1) );else{scanf( "%d",&v );update( a,b,1,n,v,1 );} }}return 0;
}