学习笔记：动态开点

Yizhixiaoyun · 2022-09-20 17:21:08 · 个人记录

博客园

什么是动态开点

我们发现，线段树的一次操作只与一个链有关，有一些节点可能是从头到尾都用不到的。所以我们可以在建树时，不开满 4 \times n 的空间，而是在使用这个点的时候才建立这个点。

例如下面这张图：

我们首先存 2 ，先从根节点 root 开始查找。

1. 发现 2 在 1-5 中，我们发现并没有这个点，那么建立。

2. 发现 2 在 1-3 中，我们发现并没有这个点，那么建立。

3. 发现 2 在 1-2 中，我们发现并没有这个点，那么建立。

4. 建立点 2。

接着存 3。

1. 发现 3 在 1-5 中，我们发现已经有这个点，不进行操作。

2. 发现 3 在 1-3 中，我们发现已经有这个点，不进行操作。

3. 建立点 3。

以此类推。

最后我们发现，点 1，点 4，点 6 没有被建立。这是数据小的情况，如果数据规模很大，省下的空间是非常可观的。

动态开点适用于什么问题

动态开点一般在 n 很大（例如 n \le 10^9）的时候使用。

动态开点的基本框架

pushup

void pushup(int o){a[o].s=a[a[o].l].s+a[a[o].r].s;}

update

跟着上文的思路走。

void update(int l,int r,int dl,int dr,int v,int &o){
    if(o==0) o=++cnt,a[o].tag=0;
    if(dl<=l&&r<=dr){
        a[o].s=v*(r-l+1);
        a[o].tag=v+1;
        return; 
    } 
    pushdown(l,r,o);
    int mid=(l+r)>>1;
    if(dl<=mid) update(l,mid,dl,dr,v,a[o].l);
    if(dr>mid) update(mid+1,r,dl,dr,v,a[o].r);
    pushup(o);
}

query

对于查询操作，遇到一个没有访问过的节点，直接返回。

int query(int l,int r,int x,int y,int o){
    if(o==0) return 0;
    if(l==x&&r==y) return c[o];
    int mid=(l+r)>>1;
    if(y<=mid) return query(l,mid,x,y,a[o].l);
    else if(x>mid) return query(mid+1,r,x,y,a[o].r);
    return query(l,mid,x,mid,a[o].l)+query(mid+1,r,mid+1,y,a[o].r);
}

实战演练

CF915E Physical Education Lessons

动态开点模板题。（当然你也可以用珂朵莉树做）