526互联

线段树高阶学习指南

发布时间 2023-10-14 08:23:51作者: White_Sheep

前置芝士

线段树基本框架

区间求和

const int N=100010;
ll a[N],st[N*4],f[N*4];
int n,q;
//向上传
void pushup(ll u){
    st[u]=st[lc]+st[rc];
}
//向下传
void pushdown(ll u,ll l,ll r,ll mid){
    if(f[u]){
        st[lc]+=f[u]*(mid-l+1);
        st[rc]+=f[u]*(r-mid);
        f[lc]+=f[u];
        f[rc]+=f[u];
        f[u]=0;
    }
}
//初始化
void build(ll u,ll l,ll r){
    if(l==r){
        st[u]=a[l];
        return;
    }
    ll mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(u);
}
//区间更新
void update(ll u,ll l,ll r,ll x,ll y,ll k){
    if(x>r||y<l) return;
    if(x<=l&&y>=r){
        st[u]+=(r-l+1)*k;
        f[u]+=k;
        return;
    }
    ll mid=l+r>>1;
    pushdown(u,l,r,mid);
    update(lc,l,mid,x,y,k);
    update(rc,mid+1,r,x,y,k);
    pushup(u);
}
//区间查询
ll query(ll u,ll l,ll r,ll x,ll y){
    if(x>r||y<l) return 0;
    if(x<=l&&r<=y) return st[u];
    ll mid=l+r>>1;
    pushdown(u,l,r,mid);
    return query(lc,l,mid,x,y)+query(rc,mid+1,r,x,y);
}
//build(1,1,n);
//update(1,1,n,l,r,k);
//query(1,1,n,l,r);

区间最值

[python]

class Tree():
    def __init__(self):
        self.l=0
        self.r=0
        self.lazy=0
        self.val=0

tree=[Tree() for i in range(10*4)]
def build(p,l,r):
    if l>r:
        return
    tree[p].l, tree[p].r, tree[p].lazy, tree[p].val = l, r, 0, 0
    if l<r:
        mid=(l+r)>>1
        build(p<<1,l,mid)
        build(p<<1|1,mid+1,r)
def pushUp(p):
    tree[p].val=max(tree[p<<1].val,tree[p<<1|1].val)


#单点修改，添加值
def add(p,i,v):
    if tree[p].l==tree[p].r:
        tree[p].val+=v
    else:
        mid=(tree[p].l+tree[p].r)>>1
        if i>mid:
            add(p<<1|1,i,v)
        else:
            add(p<<1,i,v)
        pushUp(p)
def pushdown(p):
    if tree[p].lazy:
        lazy=tree[p].lazy
        tree[p<<1].lazy+=lazy
        tree[p<<1|1].lazy+=lazy
        tree[p<<1].val+=lazy
        tree[p<<1|1].val+=lazy
        tree[p].lazy=0
def update(p,l,r, v):
    if l<=tree[p].l and r>=tree[p].r:
        tree[p].lazy+=v
        tree[p].val+=v
        return
    if r<tree[p].l or l>tree[p].r:
        return
    if tree[p].lazy:
        pushdown(p)
    update(p<<1,l,r,v)
    update(p<<1|1,l,r,v)
    pushUp(p)

def query(p,l,r):
    if l<=tree[p].l and r>=tree[p].r:
        return tree[p].val
    if tree[p].l>r or tree[p].r<l:
        return 0
    if tree[p].lazy:
        pushdown(p)
    return max(query(p<<1,l,r),max(p<<1|1,l,r))
build(1,1,10)
update(1,1,5,1)
update(1,7,10,1)
update(1,2,8,1)
update(1,3,4,1)
update(1,9,10,1)
print(query(1,1,10))

[java]

class SegTree{
    static final int INF=0x3f3f3f3f;
    final int n;
    final int[] min,lazy;

    SegTree(int n) {
        this.n=n;
        min=new int[n<<2];
        lazy=new int[n<<2];
        Arrays.fill(min,INF);
        Arrays.fill(lazy,INF);
    }
    void build(int[] a){
        build(1,0,n-1,a);
    }
    void build(int p,int l,int r,int[] a){
//        if(l>r) return;
        if(l==r){
            min[p]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid,a);
        build(p<<1|1,mid+1,r,a);
        min[p]=Math.min(min[p<<1],min[p<<1|1]);
    }
    void update(int i,int j,int val){
        if(i>j) return;
        update(i,j,val,0,n-1,1);
    }
    void update(int i,int j,int val,int st,int ed,int p){
        if(i<=st && j>=ed){
            min[p]=Math.min(min[p],val);
            lazy[p]=Math.min(lazy[p],val);
            return;
        }
        pushDown(p);
        int mid=(st+ed)>>1;
        if(i<=mid) update(i,j,val,st,mid,p<<1);
        if(j>mid) update(i,j,val,mid+1,ed,p<<1|1);
        pushUp(p);
    }
    int query(int i){
        return query(0,i,0,n-1,1);
    }
    int query(int i,int j){
        return query(i,j,0,n-1,1);
    }
    int query(int i,int j,int st,int ed,int p){
        if(i<=st && j>=ed){
            return min[p];
        }
        pushDown(p);
        int ans=INF;
        int mid=(st+ed)>>1;
        if(i<=mid) ans=Math.min(ans,query(i,j,st,mid,p<<1));
        if(j>mid) ans=Math.min(ans,query(i,j,mid+1,ed,p<<1|1));
        return ans;
    }
    void pushUp(int p){
        min[p]=Math.min(min[p<<1],min[p<<1|1]);
    }
    void pushDown(int p){
        if(lazy[p]==INF) return;
        min[p<<1]=Math.min(min[p<<1],lazy[p]);
        min[p<<1|1]=Math.min(min[p<<1|1],lazy[p]);
        lazy[p<<1]=Math.min(lazy[p<<1],lazy[p]);
        lazy[p<<1|1]=Math.min(lazy[p<<1|1],lazy[p]);
        lazy[p]=INF;
    }
}