动态开点线段树

发表于 分类于 阅读次数： Valine： 本文字数： 1.8k 阅读时长 ≈ 2 分钟

今天学校讲了这玩意。算是正式步入省选了。

觉得还不是太熟悉，有必要写一写这篇 blog。

动态开点线段树

Why to 动态开点？

下标太大、节点太多，炸空间。

离散化又需要离线，太麻烦。

于是我们动态地开点，不需要开的点就不开，减少空间开销。

这是开一个点的代码：

1
2
3
4
5
6
7
8
int add(int l,int r,...) {
    int p=++tot;
    t[p].l=l;t[p].r=r; //我习惯把 l 和 r 存进结构体里，但是在动态开点线段树中貌似没什么用

    // something you want to maintain

    return p;
}

基本操作

pushup 按照普通线段树写法模仿，把 p<<1 与 p<<1|1 换成 t[p].ls 和 t[p].rs 即可。

pushdown 同理。

插入下标为 [L,R][L,R] 的区间？这里以最大值为例。

1
2
3
4
5
6
7
8
9
void modify(int &p,int l,int r,int L,int R,int x) {
    if(!p) p=add(l,r);
    if(L<=l&&r<=R) {t[p].mx=t[p].tag=x;return ;}
    pushdown(p);
    int mid=l+r>>1; //特别地，若下标有负数，应使用 l+(r-l>>1)
    if(L<=mid) modify(t[p].ls,l,mid,L,R,x);
    if(mid<R) modify(t[p].rs,mid+1,r,L,R,x);
    pushup(p);
}

查询？这里也以最大值为例。

1
2
3
4
5
6
7
8
9
int query(int &p,int l,int r,int L,int R) {
    if(!p) return ;
    if(L<=l&&r<=R) return t[p].mx;
    pushdown(p);
    int mid=l+r>>1,ans=0; //特别地，若下标有负数，应使用 l+(r-l>>1)
    if(L<=mid) ans=max(ans,query(t[p].ls,l,mid,L,R,x));
    if(mid<R) ans=max(ans,query(t[p].rs,mid+1,r,L,R,x));
    return ans;
}

反正和线段树很像。就是每次到一个点就把它新建一下就行了。

注意有初值的话最大值得用 ST 表处理一波初值。

例题

CF915E Physical Education Lessons

珂朵莉树好题

动态开点。因为 nn 太大了，但 qq 很小，所以需要开的点很少。

动态开点线段树维护区间和、区间赋值即可。

P5459 [BJOI2016]回转寿司

由于这题 aia_i 可以为负，于是不能用双指针扫。

考虑使用前缀和。则本题就是要统计满足 L≤sumr−suml−1≤RL\le sum_{r}-sum_{l-1}\le R 的区间 [l,r][l,r] 的个数。

考虑固定 ll，求有多少种 rr。

此时的 rr 需要满足 L+suml−1≤sumr≤R+suml−1L+sum_{l-1}\le sum_r\le R+sum_{l-1}。

可以开一个动态开点的权值线段树。从后往前扫一遍，每次加入它自己的 sumisum_i 之后问线段树中在 L+sumi−1∼R+sumi−1L+sum_{i-1}\sim R+sum_{i-1} 范围内的点的个数。

也可以离散化后用权值树状数组搞

CF817F MEX Queries

珂朵莉树好题

动态开点线段树维护区间推平成 11 或 00、区间取反和区间和。

询问就在线段树上二分，看哪里的区间和小于区间中数的个数就往哪里跑。

CF803G Periodic RMQ Problem

好题。

由于 n×kn\times k 太大了，显然要动态开点。

但是在新建一个节点的时候，我们需要将它的初值赋好。

用一个 ST 表维护一下原序列的区间 min⁡\min 用来给开的点赋初值，然后就是区间推平、区间 min⁡\min 的动态开点线段树板子了。

特别地，如果开的点经过两个 nn 的段（因为题目中 nn 循环了 kk 次），那么分两段讨论即可。如果开的点跨越了整个段，那么直接用整个序列的 minmin 来赋初值。