线段树区间修改模板

对应的水题是poj3468

今天实验室的大牛说了线段树的区间修改值在求和,（其实自己线段树还没懂太多了）觉得他们好强啊,有一道这个的模板题,在这里贴一下模板代码,自己忘了就可以再来看看.

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long int
using namespace std;
const int MAXN = 2e5+1e3;
struct Node{
    int minv, addv, maxv, sumv;
}tree[MAXN<<2];
ll a[MAXN], n;
//建树        //1       0      n-1
void build(int id, int tl, int tr) {
    tree[id].addv = 0;
    if(tl==tr){
        tree[id].minv = a[tl];
        tree[id].maxv = a[tl];
        tree[id].sumv = a[tl];
    }
    else {
        int tm = tl+tr>>1;
        build(id<<1, tl, tm);//递归建树//左儿子
        build(id<<1|1, tm+1, tr);//右儿子          //*2+1的意思.
        tree[id].minv = min(tree[id<<1].minv, tree[id<<1|1].minv);
        tree[id].maxv = max(tree[id<<1].maxv, tree[id<<1|1].maxv);
        tree[id].sumv = tree[id<<1].sumv+tree[id<<1|1].sumv;
    }
}
//放下懒人标记
void pushdown(int id,int tl, int tr) {
    int& x = tree[id].addv;//用的别名
    int tm = tl+tr>>1;
    tree[id<<1].minv += x;
    tree[id<<1].maxv += x;
    tree[id<<1].addv += x;
    tree[id<<1].sumv += x*(tm-tl+1);
    tree[id<<1|1].minv += x;
    tree[id<<1|1].maxv += x;
    tree[id<<1|1].addv += x;
    tree[id<<1|1].sumv += x*(tr-tm);
    x = 0;//如果x改变,则赋给它值的也会改变
}
//增加区间和
void add(int id, int tl, int tr, int ql, int qr, int v) {
    if(ql<=tl&&tr<=qr) {
        tree[id].addv += v;
        tree[id].minv += v;
        tree[id].maxv += v;
        tree[id].sumv += v*(tr-tl+1);
        return;
    }
    if(tl<tr) pushdown(id,tl,tr);
    int tm = tl+tr>>1;
    if(tl<=qr&&tm>=ql)
        add(id<<1, tl, tm, ql, qr, v);
    if(tr>=ql&&tm+1<=qr)
        add(id<<1|1, tm+1, tr, ql, qr, v);
    if(tl<tr) {
        tree[id].minv = min(tree[id<<1].minv, tree[id<<1|1].minv);
        tree[id].maxv = max(tree[id<<1].maxv, tree[id<<1|1].maxv);
        tree[id].sumv = tree[id<<1].sumv+tree[id<<1|1].sumv;
    }
}
//求区间最小值
int query(int id, int tl, int tr, int ql, int qr) {
    if(ql<=tl&&tr<=qr) {
        return tree[id].minv;
    }
    if(tl<tr) pushdown(id,tl,tr);
    int tm = tl+tr>>1;
    int ret = (1<<31)-1;
    if(tl<=qr&&tm>=ql)
        ret = query(id<<1, tl, tm, ql, qr);
    if(tr>=ql&&tm+1<=qr)
        ret = min(ret, query(id<<1|1, tm+1, tr, ql, qr));
    return ret;
}
//求区间最大值
int queryX(int id, int tl, int tr, int ql, int qr) {
    if(ql<=tl&&tr<=qr) {
        return tree[id].maxv;
    }
    if(tl<tr) pushdown(id,tl,tr);
    int tm = tl+tr>>1;
    int ret = 0;
    if(tl<=qr&&tm>=ql)
        ret = queryX(id<<1, tl, tm, ql, qr);
    if(tr>=ql&&tm+1<=qr)
        ret = max(ret, queryX(id<<1|1, tm+1, tr, ql, qr));
    return ret;
}
//求区间和
int querysum(int id, int tl, int tr, int ql, int qr)
{
    if(ql<=tl&&tr<=qr)
    {
        return tree[id].sumv;
    }
    if(tl<tr) pushdown(id, tl, tr);
    int tm = tl+tr>>1;
    int ret = 0;
    if(tl<=qr&&tm>=ql)
        ret = querysum(id<<1, tl, tm, ql, qr);
    if(tr>=ql&&tm+1<=qr)
        ret += querysum(id<<1|1, tm+1, tr, ql, qr);
    return ret;
}

int main(){
    int Q;
    char str[5];
    scanf("%d %d", &n , &Q);
    for(int i=0; i<n; ++i){
        scanf("%d", a+i);
    }
    int l,r,k;
    build(1, 0, n-1);
    for(int i=0;i<Q;i++){
        scanf("%s",str);
        if(str[0]=='Q'){
            scanf("%d %d",&l,&r);
            printf("%d\n",querysum(1,0,n-1,l-1,r-1));//因为建树是从0开始的,而询问是加了一的,所以要减一.
        }
        else if(str[0]=='C'){
            scanf("%d%d%d",&l,&r,&k);
            add(1,0,n-1,l-1,r-1,k);//别忘减一.
        }
    }
}