美文网首页数据结构
线段树区间修改模板

线段树区间修改模板

作者: Anxdada | 来源:发表于2017-02-23 16:07 被阅读167次

    对应的水题是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);//别忘减一.
            }
        }
    }
    

    相关文章

      网友评论

        本文标题:线段树区间修改模板

        本文链接:https://www.haomeiwen.com/subject/qesbwttx.html