线段树

十月 01, 2021

线段树

~~一种我琢磨了很长时间才明白的数据结构~~
核心思想就是把一个序列，分成一个二叉树，叶子节点存的是每个元素，能够快速修改或访问区间中的数值，~~功能♂强大~~
线段树主要分为下面几步：

push_up操作

1
2
3

void push_up(int p){
    tree[p]=tree[lc(p)]+tree[rc(p)];
}

这个很简单

build操作

void build(int l,int r,int p){
    if(l==r){
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,lc(p));
    build(mid+1,r,rc(p));
    push_up(p);
}

其实就是一个递归
先建左子树，再建右子树，最后合并起来更新根节点

但是这里我们要注意哈，如果你是像我一样以这种形式

1 2	int a[N],n,m,tree[N<<2],tag[N<<2]; int x,y,k;

存树的话,那么build操作就没别的事了
还有的大佬是把每个节点的.l=cnt 这种形式的，那么还得进行其他操作，具体看别的大佬的博客，当然，我的这种方式是空间最小的

下面一步就是核心了（

pushdown操作

我们把一个tag数组，或者叫它lazy数组，来省事，这么想，如果多次修改了同一个点的大小，我们每次子啊那么大的一个树里，改那么多数看起来是不是很亏，那么不妨在查询之前，我们先把这些要加的数存起来，等到一定时刻需要查询时再加

但是这样有个问题，这些数我们存到哪呢？
伟大的OIer先辈们早已给我们整理好了

如果节点p加上了k
那么先让tree[p]+=k;然后让tag[p]也加上k，

等到需要的时候，我们把这个p传下去，然后让下面的节点的tag[lc(p)]+=k,
这是我们看小标题，这个操作叫做pushdown（push：推，down：下面）（推下去）
那么我们就可以考虑，推下去以后子树 tree会变，tag会变，我们分别改一下，tag刚才其实已经改过了，只需要该tree就行了，tree更好改了，tag[p]存的是欠下面的数，然后子树的tree就要加上tag[p]* （子树的长度）
此时这个根节点已经做到应该做的了,所以tag[p]=0;
最后放上代码

void pushdown(int l,int r,int p){
    int mid=(l+r)>>1;
    if(tag[p]){
        tag[lc(p)]+=tag[p];
        tag[rc(p)]+=tag[p];
        tree[lc(p)]+=tag[p]*(mid-l+1);
        tree[rc(p)]+=tag[p]*(r-mid);
        tag[p]=0;
    }
}

update和query 区间修改和区间查询就直接背就行了

void update(int l,int r,int k,int m,int n,int p){
    //把l到r这段区间全部加k，总区间为m,n
    if(l<=m&&n<=r){
        tree[p]+=(n-m+1)*k;
        tag[p]+=k;
        return ;
    }
    int mid=(m+n)>>1;
    pushdown(m,n,p);
    if(l<=mid) update(l,r,k,m,mid,lc(p));
    if(r>mid) update(l,r,k,mid+1,n,rc(p));
    push_up(p);
}

int query(int l,int r,int m,int n,int p){
    if(l<=m&&n<=r) return tree[p];
    int mid=(m+n)>>1;
    pushdown(m,n,p);
    int sum=0;
    if(l<=mid) sum+=query(l,r,m,mid,lc(p));
    if(r>mid) sum+=query(l,r,mid+1,n,rc(p));
    return sum;
}

完结撒花

查看评论