codevs 1082 线段树练习3
链接：http://codevs.cn/problem/1082/
sumv是维护求和的线段树，addv是标记这歌节点所在区间还需要加上的值。
我的线段树写法在运用的时候，需要更新或查找的区间是储存在y1,y2变量里面的，值是储存在变量v里面的，查询结果储存在变量_sum里面。
每次更新（调用update函数）时，必须要维护更新区间上层的线段树，即更新节点上面的线段树表示的和是准确的和。
在update函数更新的时候，如果线段树分成区间包含于所要求的区间那么直接在addv上记录下要加的值，否则再次细分区间。最后要再维护一下（调用pushdown函数），这样就保证了线段树的和性质。
pushdown函数非常重要，在我的写法里，它有两个作用，一个是标记下放，另一个是结算和维护。注意在结算和的时候，要把左右儿子的addv和的也要加上去，否则会漏值。查询的时候也要用到pushdown，否则addv的值会在细分区间的时候漏掉，但查询（query函数）的pushdown不太样，要加入一个判断：只有当addv值不为0的时候才标记下放。如果不这样，本来一个对的值就会被重新计算，从而破坏了线段树的性质。
附上代码：
#include<cstdio>
#include<iostream>
#define LL long long int
using namespace std;
const int maxn=; LL n,k,A[maxn],sumv[maxn*],addv[maxn*]; void init(int o,int L,int R)//初始化建树
{
if(L==R) sumv[o]=A[L];
else
{
int M=(L+R)/;
init(o*,L,M);
init(o*+,M+,R);
sumv[o]=sumv[o*]+sumv[o*+];
}
} void pushdown(int o,int L,int R)//标记下放
{
int M=(L+R)/;
if(L!=R) sumv[o]=sumv[o*]+sumv[o*+]+addv[o]*(R-L+)+addv[o*]*(M-L+)+addv[o*+]*(R-M);
else sumv[o]+=addv[o];
addv[o*]+=addv[o];
addv[o*+]+=addv[o];
addv[o]=;
} int y1,y2,v;
void update(int o,int L,int R)//更新
{
if(y1<=L && R<=y2) addv[o]+=v;
else
{
int M=(L+R)/;
if(y1<=M) update(o*,L,M);
if(y2>M) update(o*+,M+,R);
}
pushdown(o,L,R);
} LL _sum,p;
void query(int o,int L,int R)//查询
{
if(addv[o]!=) pushdown(o,L,R);
if(y1<=L && R<=y2) _sum+=sumv[o];
else
{
int M=(L+R)/;
if(y1<=M) query(o*,L,M);
if(y2>M) query(o*+,M+,R);
}
} int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>A[i];
init(,,n);
cin>>k;
for(int i=,tp,x,y,z;i<=k;i++)
{
cin>>tp;
if(tp==)
{
cin>>x>>y>>z;
y1=x,y2=y,v=z;
update(,,n);
}
else
{
cin>>x>>y;
y1=x,y2=y,_sum=;
query(,,n);
cout<<_sum<<endl;
}
}
return ;
}