求赞qwq

线段树的动态开点用于解决：

线段所包含的区间为 $[-1e9,1e9]$,$[0,1e9]$ 之类的题目(当然实际生成节点的开销不会MLE)

case

最常见的是线段树解决普通平衡树的题目。

用线段树解决这类区间特别大，但是实际节点数为 $n\log n$ 的问题一般有两种方法:

• 离散化
• 动态开点

下面简单介绍我对动态开点的认知:

初始状态:

• 动态开点的上界 $Up$ 与下界 $Down$ 是基于题目中数据的大小
• 起初存在 区间0 ,它包含的区间为 $[Down,Up]$

在介绍修改与查询操作较之前普通线段树的操作的不同之前，先看看 $pushdown$ 的改进

单点 pushdown

void pushdown(int u)
{
    if(!lc[u]) lc[u] = ++ idx;
    if(!rc[u]) rc[u] = ++ idx;
}

• lc[u] : 表示 $u$ 的左子节点的位置
• rc[u] : 表示 $u$ 的右子节点的位置

区间 pushdown

void pushdown(int u,int len)
{
    if(!lc[u]) lc[u] = ++ idx,tr[lc[u]].len = len - len / 2;
    if(!rc[u]) rc[u] = ++ idx,tr[rc[u]].len = len / 2;
    xxx(懒标记的相关操作)
}

注意这里的给左子节点，右子节点分配的 $len$ 与某样东西具有对应性

单点修改:

void modify(int u,int l,int r,int x,int c)
{
    /*
    l : 当前线段的左端点
    r : 当前线段的右端点
    */
    if(l == r) return void(v[u] = max(v[u],c));
    pushdown(u);
    int mid = l + r >> 1;
    if(x <= mid) modify(lc[u],l,mid,x,c);
    else modify(rc[u],mid + 1,r,x,c);
    pushup(u);
}

本质上是基于 $[Down,Up]$ 区间不断二分，直至二分到 $x$ 这一点，然后对这一点 $+d$

区间修改

void modify(int u,int l,int r,int L,int R,int d)
{
    if(L <= l && r <= R) 
        return void((tr[u].tag += d,tr[u].v += (r - l + 1LL) * d));
    if(r < L || l > R) return;
    pushdown(u,r - l + 1);
    int mid = l + r >> 1;
    if(l <= mid) modify(lc[u],l,mid,L,R,d);
    if(r > mid) modify(rc[u],mid + 1,r,L,R,d);
    pushup(u);
}

这里注意两个出口条件以及:

$len = r - l + 1$

• mid = l + r >> 1 对应 $[l,mid]$ 的长度为 $len- len / 2$(下取整)
• mid = l + r - 1 >> 1 对应 $[l,mid]$ 的长度为 $len / 2$(下取整)

需要证明的话可以将下取整除法通过 $a/^*b$ = $\displaystyle{\frac{a - a \% b}{b}}$转换进行证明，或者举例

类似地，区间查询(单点查询可以根据单点修改代码得到):

LL ask(int u,int l,int r,int L,int R)
{
    if(L <= l && r <= R) return tr[u].v;
    if(r < L || l > R) return 0;
    pushdown(u,r - l + 1);
    int mid = l + r  >> 1;LL res = 0;
    if(l <= mid) res = ask(lc[u],l,mid,L,R);
    if(r > mid) res += ask(rc[u],mid + 1,r,L,R);
    return res;
}

补充:

• 需要开的节点数量: $2n\log n$($n$为查询的数量)

cases

1. 普通平衡树
2. CF915E