动态开点
Tarsal
·
·
个人记录
动态开点
什么是动态开点，是用于处理一些区间跨度比较大，空间比较小的题目。
比如：
肯定是不可以直接建，那样空间会炸。
所以有 $2$ 中办法：
$1.$ 离散化
这个办法是很早就开始用了的，也比较有效。
$2.$ 动态开点
当你遇到题目要求强制在线的时候怎么办呢？
就不能离散化了啊。
这就开始动态开点了。。。
首先，在原问题中，你需要解决的问题是：
内存不足并且有很多的无用节点。
那你就不给他内存就行了啊
你就不一定想平常那样子 $x << 1$ 和 $x << 1 | 1$ 的建树
把每个需要用的节点的左右节点都用数组记录下来。
其他不需要用的节点就不给他分配内存。
具体的话，可以看看这段伪代码代码：
```
int Build(int l, int r) { int now = inc(rt);
if(l < r) { L[now] = Build(l, mid), R[now] = Build(mid + 1, r);}
return now;
}
int Updata(int pre, int l, int r, int x) { int now = inc(rt);
L[now] = L[pre], R[now] = R[pre], Data[now] = Data[pre] + 1;
if(l < r) {if(x <= mid) L[now] = Updata(L[pre], l, mid, x);
else R[now] = Updata(R[pre], mid + 1, r, x);}
return now;
}
int main() {
T[0] = build(1, m);
Rep(i, 1, n) T[i] = updata(T[i - 1], 1, m, a[i]);
………………
return 0;
}
```