动态开点线段树

· · 算法·理论

众所周知，线段树数组的大小是 4n，也就是要维护的范围的四倍，但是当 n 很大时，就开不了了，所以诞生了动态开点线段树

动态开点线段树没有建树函数，需要用到哪个节点就开哪个，并存储其维护的范围（l,r），没有固定的k << 1，k << 1 | 1了

这样的一棵线段树可以维护负数，但对应的为了处理负数，mid 的值变成了 (l+r-1)/2

其他的就和普通线段树没什么区别了，但因为它作用于维护范围大的时候，所以一般和权值线段树结合

这里有个问题，所以此时线段树数组要开多大？建议开最大值，因为这是个玄学问题，有的时候 qlogn 不够大会RE，所以不妨开到 10^7 级别

关于正确性：可以理解为原先这棵树是虚的，用到哪个节点就把哪个变成现实的，就好像在树上加边加点，对于线段树就体现为左右端点

现在我们来说一下函数（因为通常维护的值较大所以开了全局long long），以单点修改+区间查询为例，这时不需要用lazytag

单点修改

除了和一个点维护的左右端点 ls,rs 有关的要改变，其余不动

因为这时 k 的值不一定已知，所以要有一个计数器 cnt 用于建立新的节点编号更新 k，再就是 mid 的处理和宏的定义了

函数参数：&k 的意思是 k 在函数内值的改动是要保留的；把 l,r 放后面是因为有时要在函数内赋固定的初值 MN,MX，调用函数时不写，所以放后面不会报错

void mdf(long long &k,long long x,long long v,long long l,long long r)
{
    if(k == 0)
    {
        k = ++cnt;//这里k的值可改变，所以相当于用到了当前节点就要建上
    }
    if(l == r)
    {
        s[k].sum += v;
        return;
    }
    long long mid = (l + r - 1) / 2;//细节，为了处理负数，线段树里所有mid都改成这样
    if(x <= mid)
    {
        mdf(ls(k),x,v,l,mid);//ls(k)=s[k].l，为了方便
    }
    else
    {
        mdf(rs(k),x,v,mid + 1,r);//rs(k)=s[k].r
    }
    s[k].sum = s[ls(k)].sum + s[rs(k)].sum;
}

区间查询

同上，只改动了和 ls,rs 相关的代码

注意在查询的时候也要不断建立新节点，因为不一定在修改时已经遍历过

long long query(long long &k,long long x,long long y,long long l,long long r)//写法同上
{
    if(k == 0)
    {
        k = ++cnt;//建立新节点
    }
    if(x <= l && r <= y)
    {
        return s[k].sum;
    }
    long long mid = (l + r - 1) / 2,ans = 0;
    if(x <= mid)
    {
        ans += query(ls(k),x,y,l,mid);
    }
    if(y > mid)
    {
        ans += query(rs(k),x,y,mid + 1,r);
    }
    return ans;
}

pushdown

这里放一下，有区间修改时使用，和普通版的区别是，如果没有左右子节点，那么就要新建一个进行标记下传

void pd(int k,int l,int r)
{
    if(s[k].lz != -1)//有的是区间覆盖为0，所以初值设为-1判断
    {
        int mid = (l + r - 1) / 2;
        if(ls(k) == 0)//标记下传也要更新节点，这是左
        {
            ls(k) = ++cnt;
        }
        if(rs(k) == 0)//这是右
        {
            rs(k) = ++cnt;
        }
        s[ls(k)].lz += s[k].lz;//懒标记下传
        s[rs(k)].lz += s[k].lz;
        s[ls(k)].sum += s[k].lz * (mid - l + 1);//sum（维护的值）下传
        s[rs(k)].sum += s[k].lz * (r - mid);
        s[k].lz = -1;
    }
}

函数调用

显然上面两个函数都是动态开点权值线段树，所以调用也应该和权值线段树一样，l,r 写值域

但是这里要注意 k，调用时用一个变量 rt 来充当初始的 k，因为这个值没什么意义，但 rt 的初值一定一定要设为 0，不然会在一棵空树的时候判断已经有节点建立了

例题

例1：P5459

题目

题目相当于找有哪些区间区间合在 [L,R] 之间，使用前缀和优化，推推式子：（设前缀和数组为 b）

L \le b_r-b_{l-1} \le R =>L+b_{l-1} \le b_r \le R+b_{l-1} =>$ 对于每个 $b_{l-1}$ 要找符合要求的 $b_r

不难想到倒序遍历 b 数组，每次加入 b_i，并让答案加上此时区间 [L+b_{i-1},R+b_{i-1}] 内的数个数

根据数据范围发现 b 值的大小在 [-10^{10},10^{10}] 之间，果断开权值线段树，由于空间爆炸再套上动态开点，那么就是单点修改+区间查询

这里函数的参数 l,r 就是全局固定的，那么每次直接在函数参数那里赋初值 [-10^{10},10^{10}] 就行

这个题数组大小就玄学，直接开了个 10^7-1 才过的……

Code: 
#include <bits/stdc++.h>
using namespace std;
#define ls(k) s[k].l
#define rs(k) s[k].r
long long n,d,u,a[100005],b[100005],cnt,MX = 1e10;
struct node
{
    long long l,r,sum;
}s[99999999];
void mdf(long long &k,long long x,long long v,long long l = -MX,long long r = MX)
{
    if(k == 0)
    {
        k = ++cnt;
    }
    if(l == r)
    {
        s[k].sum += v;
        return;
    }
    long long mid = (l + r - 1) / 2;
    if(x <= mid)
    {
        mdf(ls(k),x,v,l,mid);
    }
    else
    {
        mdf(rs(k),x,v,mid + 1,r);
    }
    s[k].sum = s[ls(k)].sum + s[rs(k)].sum;
}
long long query(long long &k,long long x,long long y,long long l = -MX,long long r = MX)
{
    if(k == 0)
    {
        k = ++cnt;
    }
    if(x <= l && r <= y)
    {
        return s[k].sum;
    }
    long long mid = (l + r - 1) / 2,ans = 0;
    if(x <= mid)
    {
        ans += query(ls(k),x,y,l,mid);
    }
    if(y > mid)
    {
        ans += query(rs(k),x,y,mid + 1,r);
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld",&n,&d,&u);
    for(long long i = 1;i <= n;i++)
    {
        scanf("%lld",&a[i]);
        b[i] = b[i - 1] + a[i];
    }
    long long rt = 0,ans = 0;
    for(long long i = n;i >= 1;i--)
    {
        mdf(rt,b[i],1ll);
        ans += query(rt,d + b[i - 1],u + b[i - 1]);
    }
    printf("%lld",ans);
    return 0;
}

例2：CF915E

题目

初始都是工作日，易想到去维护非工作日，答案就是总天数 - 非工作日天数，那么这个题本质上就是一个区间覆盖+区间求和的问题

注意到 n \le 10^9，说明要开权值线段树，同时动态开点减小空间，因为是覆盖问题所以不用开long long，是 = 而非 +=

但是这个毒瘤题卡常，要写快读，本喵不会所以悲惨TLE #7，想过要去写珂朵莉树qaq

Code: 
#include <bits/stdc++.h>
using namespace std;
#define ls(k) s[k].l
#define rs(k) s[k].r
int n,q,cnt;
struct tree
{
    int l,r,lz = -1,sum;
}s[9999999];
void pd(int k,int l,int r)
{
    if(s[k].lz != -1)//这里如果初值为0就错了，无法区间覆盖0
    {
        int mid = (l + r - 1) / 2;
        if(ls(k) == 0)
        {
            ls(k) = ++cnt;
        }
        if(rs(k) == 0)
        {
            rs(k) = ++cnt;
        }
        s[ls(k)].lz = s[k].lz;
        s[rs(k)].lz = s[k].lz;
        s[ls(k)].sum = s[k].lz * (mid - l + 1);
        s[rs(k)].sum = s[k].lz * (r - mid);
        s[k].lz = -1;
    }
}
void mdf(int &k,int x,int y,int v,int l,int r)
{
    if(k == 0)
    {
        k = ++cnt;
    }
    if(x <= l && r <= y)
    {
        s[k].lz = v;
        s[k].sum = v * (r - l + 1);
        return;
    }
    pd(k,l,r);
    int mid = (l + r - 1) / 2;
    if(x <= mid)
    {
        mdf(ls(k),x,y,v,l,mid);
    }
    if(y > mid)
    {
        mdf(rs(k),x,y,v,mid + 1,r);
    }
    s[k].sum = s[ls(k)].sum + s[rs(k)].sum;
}
int query(int &k,int x,int y,int l,int r)
{
    if(k == 0)
    {
        k = ++cnt;
    }
    if(x <= l && r <= y)
    {
        return s[k].sum;
    }
    pd(k,l,r);
    int mid = (l + r - 1) / 2,ans = 0;
    if(x <= mid)
    {
        ans += query(ls(k),x,y,l,mid);
    }
    if(y > mid)
    {
        ans += query(rs(k),x,y,mid + 1,r);
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&q);
    int rt = 0;
    while(q--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        if(k == 1)
        {
            mdf(rt,l,r,1ll,1,n);
        }
        else
        {
            mdf(rt,l,r,0ll,1,n);
        }
        printf("%d\n",n - query(rt,1,n,1,n));
    }
    return 0;
}

例3：CF817F

题面

这题挺难评的，也不算严格的动态开点线段树，只能说是离散化+进阶懒标记，只是开个结构体记录一下区间端点而已

题目相当于两种操作：区间覆盖为 0,1 和区间翻转，显然需要维护屎山懒标记

开一个结构体表示线段树，要有变量 l,r,lz,sum，表示区间的左右端点、懒标记以及区间和

考虑懒标记怎么设立，这东西是用于将上层节点中的修改操作，等到pushdown时再下传给子节点，并把当前节点的清空，感性理解为延迟更新操作（过年长辈收红包不肯发给小辈直到更大的长辈来检查），所以要保证它的值可以和修改操作一一对应

重点：懒标记代表的修改状态是这个节点刚刚“被修改”过的，还没给子节点下传的，也就是说假设懒标记代表要覆盖为 0 那当前区间和一定为 0

不妨设 lz=0 表示没有操作，lz=1 表示用 0 覆盖区间，lz=2 表示用 1 覆盖区间，lz=3 表示翻转区间

pushdown函数要分类讨论先判断当前节点 lz \ne 0 且非叶子结点，如果 lz \ne 3 这是最简单的情况，直接按照区间覆盖修改左右端点的 lz,sum 即可；反之，需要对于左右端点的 lz=0/1/2/3 分类讨论：

  1. 看来子节点并没有存储懒标记，直接反转该区间和，并将它的 lz 设为 3
  2. 这说明它要把下面的区间都改成 0，且自身现在和为 0，那么把它的区间和改成区间长度（每个元素都是 1），且 lz 改成 2
  3. 和 lz=1 相反，于是把区间和改成 0，向下的懒标记被不幸改成了覆盖 0 的状态 1
  4. 这代表还未下传的反转标记可以撤回啦，不过还要把当前区间和 sum 改成 len-sum

BUT，真的需要这么麻烦吗？？

结论：不管怎样区间和都要反转，而 lz 则变成了 3-lz

因为如果没有懒标记则需要反转，如果已经是反转则抵消了，覆盖成 0/1 刚好相反

终于，写完了标记下传，我忒难了QAQ

现在来考虑mdf函数，mdf1是普普通通的区间覆盖，mdf2是奇奇怪怪的区间反转，当前节点对应的区间被修改区间完全包含时直接上前面的结论，改当前节点维护的值

说说query，对于一个区间 [l,r]，如果区间和是 0 则 MEX（没有出现过的最小正整数）就是 l；如果是区间长度，则表示 MEX 不在当前区间内；如果都不是，则分别查询左、右子节点对应的区间

这里因为不可能维护 10^{18} 的区间，所以要离散化，考虑到有可能出现整个区间都是 0/1 或者最终答案是 1 但和任意区间都不相接的情况，所以要读入操作数组 a 后，要有一个数组 b 存储下每个操作区间的 l,r,l-1,r+1 和最后的一个单个 1

离散化时不但要将数组整体缩到 [1,4*n+1] 范围内，还要记录变小的值对应的原数（因为要求 MEX）

每次修改操作按照离散化后的区间执行，而查询操作输出当前被缩小的值对应的原数

Code: 
#include <bits/stdc++.h>
using namespace std;
#define ls(k) s[k].l
#define rs(k) s[k].r
long long n,b[3000005],c[3000005],d[3000005];
struct node
{
    long long f,l,r;
}a[3000005];
struct tree
{
    long long l,r,lz,sum;
}s[2000005];
void build(long long k,long long l,long long r)
{
    ls(k) = l;
    rs(k) = r;
    if(l == r)
    {
        return;
    }
    long long mid = (l + r) / 2;
    build(k << 1,l,mid);
    build(k << 1 | 1,mid + 1,r);
}
void pd(long long k,long long l,long long r)
{
    if(s[k].lz != 0 && ls(k) != rs(k))
    {
        if(s[k].lz != 3)
        {
            s[l].lz = s[k].lz;
            s[l].sum = (s[k].lz - 1) * (rs(l) - ls(l) + 1);
            s[r].lz = s[k].lz;
            s[r].sum = (s[k].lz - 1) * (rs(r) - ls(r) + 1);
        }
        else
        {
            s[l].lz = 3 - s[l].lz;
            s[l].sum = rs(l) - ls(l) + 1 - s[l].sum;
            s[r].lz = 3 - s[r].lz;
            s[r].sum = rs(r) - ls(r) + 1 - s[r].sum;
        }
        s[k].lz = 0;
    }
}
void mdf1(long long k,long long x,long long y,long long v)
{
    if(x <= ls(k) && rs(k) <= y)
    {
        s[k].lz = v;
        s[k].sum = (v - 1) * (rs(k) - ls(k) + 1);
        return;
    }
    pd(k,k << 1,k << 1 | 1);
    long long mid = (ls(k) + rs(k)) / 2;
    if(x <= mid)
    {
        mdf1(k << 1,x,y,v);
    }
    if(mid < y)
    {
        mdf1(k << 1 | 1,x,y,v);
    }
    s[k].sum = s[k << 1].sum + s[k << 1 | 1].sum;
}
void mdf2(long long k,long long x,long long y)
{
    if(x <= ls(k) && rs(k) <= y)
    {
        s[k].lz = 3 - s[k].lz;
        s[k].sum = rs(k) - ls(k) + 1 - s[k].sum;
        return;
    }
    pd(k,k << 1,k << 1 | 1);
    long long mid = (ls(k) + rs(k)) / 2;
    if(x <= mid)
    {
        mdf2(k << 1,x,y);
    }
    if(mid < y)
    {
        mdf2(k << 1 | 1,x,y);
    }
    s[k].sum = s[k << 1].sum + s[k << 1 | 1].sum;
}
long long query(long long k)
{
    if(s[k].sum == 0)
    {
        return ls(k);
    }
    if(s[k].sum == rs(k) - ls(k) + 1)
    {
        return 0;
    }
    pd(k,k << 1,k << 1 | 1);
    long long x = query(k << 1);
    if(x != 0)
    {
        return x;
    }
    x = query(k << 1 | 1);
    return x;
}
int main()
{
    scanf("%lld",&n);
    for(long long i = 1;i <= n;i++)
    {
        scanf("%lld%lld%lld",&a[i].f,&a[i].l,&a[i].r);
        b[(i - 1) * 4 + 1] = a[i].l;
        b[(i - 1) * 4 + 2] = a[i].l - 1;
        b[(i - 1) * 4 + 3] = a[i].r;
        b[i * 4] = a[i].r + 1;
    }
    b[n * 4 + 1] = 1;//防止出现1 0 0 1 ...
    sort(b + 1,b + n * 4 + 2);
    long long cnt = 0;
    for(long long i = 1;i <= n * 4 + 1;i++)
    {
        if(b[i] != b[i - 1])
        {
            c[b[i]] = ++cnt;//离散化后的值
            d[cnt] = b[i];//对应的原数
        }
    }
    build(1,1,cnt);
    for(long long i = 1;i <= n;i++)
    {
        if(a[i].f != 3)
        {
            mdf1(1,c[a[i].l],c[a[i].r],3 - a[i].f);
        }
        else
        {
            mdf2(1,c[a[i].l],c[a[i].r]);
        }
        printf("%lld\n",d[query(1)]);//显然此时query返回的不是答案
    }
    return 0;
}