标记延迟和标记下传 线段树

· · 个人记录 

//1.建树
void build(int k,int l,int r){
    //当前结点编号k   区间[l,r]
    //如果走到了叶子结点  l和r相等
    if(l==r){
        mi[k]=v; //对应区间的最小值为原序列中的值
        return ; 
    } 
    int mid=(l+r)/2;
    build(k*2,l,mid); //构造左子树 
    build(k*2+1,mid+1,r); //构造右子树 
    mi[k]=min(mi[k*2],mi[k*2+1]);//自下而上更新当前点的min值  
} 
//2.区间查询最小值
int query_min(int k,int l,int r,int x,int y){
    //k:当前点的编号 [l,r]当前点负责区间  [x,y]查询的区间 
    //查询的区间和这个点区间毫无交集  返回一个不影响答案的值 本例子返回无穷大
    if(r<x||l>y) return 2147483647;
    //查询的区间包含了 这个点的区间   返回这个点的mi值
    if(l>=x&&r<=y) return mi[k];
    //包含但没完全包含 只包含了亿点点
    int mid=(l+r)/2;
    return min(query_min(k*2,l,mid,x,y),query_min(k*2+1,mid+1,r,x,y)); 
} 
//3.单点修改 
void change(int k,int l,int r,int x,int v){
    //把a[x]的值改为v
    //编号x 在区间[l,r]外面   当前点负责的区间和被修改元素毫无毫无交集 
    if(r<x||l>x) return ;
    if(l==r&&l==x){//当前点是对应的叶子结点 
        mi[k]=v;
        return ;
    } 
    int mid=(l+r)/2;
    change(k*2,l,mid,x,v);
    change(k*2+1,mid+1,r,x,v);
    mi[k]=min(mi[k*2],mi[k*2+1]); 
} 

//灵长类碳基哺乳动物都能李姐的线段树模板

//延迟标记 增强 区间修改 单点查询
int query(int k,int l,int r,int p) {//查询第p个元素的值 
    if(l==r) return addsum[k]; //叶子结点
    int mid=(l+r)/2;
    if(p<=mid) return query(k*2,l,mid,p)+addsum[k];
    else return query(k*2+1,mid+1,r,p)+addsum[k]; 
}

void modify(int k,int l,int r,int x,int y,int v){
    if(l>y||r<x) return ;
    if(l>=x&&r<=y){
        addsum[k]+=v;
        return ;
    }
    int mid=(l+r)>>1;
    modify(k*2,l,mid,x,y,v);
    modify(k*2+1,mid+1,r,x,y,v);
}

//标记下传 区间修改 区间查询
void Add(int k,int l,int r,int v){//给区间[l,r]所有元素都加上v 
    add[k]+=v;                    //打标记 
    sum[k]+=(r-l+1)*v;            //维护更新对应的区间和 
    return ;
} 

void pushdown(int k,int l,int r,int mid){
    if(add[k]==0) return ;//没有标记 不用管
    Add(k*2,l,mid,add[k]);      //下传左子树 
    Add(k*2+1,mid+1,r,add[k]);  //下传右子树 
    add[k]=0;          //清空标记 
} 

void modify(int k,int l,int r,int x,int y,int v){//给[x,y]都加上v
    if(l>=x&&r<=y) return Add(k,l,r,v);
    int mid=l+r>>1;
    pushdown(k,l,r,mid); //到达每一个点都要下传标记
    if(x<=mid) modify(k*2,l,mid,x,y,v);
    if(mid<y) modify(k*2+1,mid+1,r,x,y,v);
    sum[k]=sum[k*2]+sum[k*2+1]; 

} 

int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return sum[k];
    int mid=l+r>>1,res=0;
    pushdown(k,l,r,mid);              //下传标记 
    if(x<=mid) res+=query(k*2,l,mid,x,y);
    if(mid<y) res+=query(k*2+1,mid+1,r,x,y);
                                           //不需要更新区间和 因为子结点没发生修改 
    return res;
}

//灵长类碳基哺乳动物都能李姐的线段树模板 增强版