codevs 1082 线段树区间求和

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 ;

  }

巴特西

codevs 1082 线段树区间求和

最新文章

热门文章