树——区间查询和修改问题————线段树（模板1.0）

￡神魔★判官ぃ 2024-04-17 16:19 48阅读 0赞

##### 普通区间修改和查询 （带懒惰标记）模板 #####

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+50;
    struct node
    { 
        int l, r;//区间左右端点
        int sum;//区间信息, 可以是最值、 区间和、等等
        int lazy;//懒惰标记 
    }Segtr[maxn*4];// 开4倍空间， 这个是大佬们计算出的
    
    void pushdown(int rt)// 懒惰标记下压函数
    { 
        /******** 此处有更新操作， 按照题意 ***********/
        //下压标记
        Segtr[rt*2+1].lazy = Segtr[rt].lazy;
        Segtr[rt*2+2].lazy = Segtr[rt].lazy;
        Segetr[rt].lazy = 0;
    }
    void pushup(int rt)
    { 
        Segtr[rt].sum = Segtr[rt*2+1].sum+Segtr[rt*2+2].sum;//回溯更新操作， 按照题意
    }
    void build(int l, int r, int rt)// 分别表示区间的左右端点， 和区间对应结点的编号
    { 
        //初始化
        Segtr[rt].l = l;
        Segtr[rt].r = r;
        Segtr[rt].lazy = 0;
        Segtr[rt].sum = 0;
        if(l == r)return;//递归到叶子结点返回
        int mid = (l+r)/2; //可以换成（l+r）>>1;
        build(l, mid, rt*2+1);//建立左子树
        build(mid+1, r, rt*2+2);//建立右子树
        pushup(rt);// 回溯维护父结点
    }
    void update(int L, int R, int rt, int v)//分别表示要更新区间额左右端点 和对应的结点编号， 和更新的值
    { 
        int l = Segtr[rt].l;
        int r = Segtr[rt].r;
        
        if(l == L&& r == R)// 找到要更细的直接区间，将其更新， 然后打上标记
        { 
            Segtr[rt].sum += (R-L+1)*add;
            Segtr[rt].lazy +=add;
            return;
        }
        if(Segtr[rt].lazy) pushdown(rt); //如果有标记就下压标记
        int mid = (l+r)/2;
        if(R <= mid) update(L, R, rt*2+1, add);
        else if(L > mid) update(L, R, rt*2+2, add);
        else 
        { 
           update(L, mid, rt*2+1, add);
           update(mid+1, R, rt*2+2, add);
        }
        
        pushup(rt); //回溯维护父亲
    }
    int query(int L, int R, int rt)// 查询函数
    { 
        int res = 0;
        int l = Segtr[rt].l;
        int r = Segtr[rt].r;
        
        if(l == L && r == R)
        { 
            return Segtr[rt].sum;
        }
        if(Segtr[rt].lazy)pushdown(rt);
        
        int mid = (l+r)/2;
        
        if(R <= mid)res+=query(L, R, rt*2+1);
        else if(L > mid)res+=query(L, R, rt*2+2);
        else
        { 
            res+=query(L, mid, rt*2+1);
            res+=query(mid+1, R, rt*2+2);
        }
        return res;
    }
    int main()
    { 
        
        
        return 0;
    }