|
|
|
|
|
|
|
|
## 动态开点线段树
|
|
|
我们发现，线段树的一次操作只与一个链有关，有一些节点可能是从头到尾都用不到的。所以我们可以在建树时，不开满 $4×n$ 的空间，而是在使用这个点的时候才建立这个点。
|
|
|
|
|
|
例如下面这张图：
|
|
|
|
|
|
|
|
|
|
|
|
我们首先存 $2$ ，先从根节点 $root$ 开始查找。
|
|
|
|
|
|
发现 $2$ 在 $1−5$ 中，我们发现并没有这个点，那么建立。
|
|
|
|
|
|
发现 $2$ 在 $1−3$ 中，我们发现并没有这个点，那么建立。
|
|
|
|
|
|
发现 $2$ 在 $1−2$ 中，我们发现并没有这个点，那么建立。
|
|
|
|
|
|
建立点 $2$。
|
|
|
|
|
|
接着存 $3$。
|
|
|
|
|
|
发现 $3$ 在 $1−5$ 中，我们发现已经有这个点，不进行操作。
|
|
|
|
|
|
发现 $3$ 在 $1−3$ 中，我们发现已经有这个点，不进行操作。
|
|
|
|
|
|
建立点 $3$。
|
|
|
|
|
|
以此类推。
|
|
|
|
|
|
最后我们发现，点 $1$，点 $4$，点 $6$ 没有被建立。这是数据小的情况，如果数据规模很大，省下的空间是非常可观的。
|
|
|
|
|
|
#### 动态开点适用于什么问题
|
|
|
动态开点一般在 $n$ 很大（例如 $n≤10^9$）的时候使用。
|
|
|
|
|
|
#### 带累加懒标记的动态开点线段树模板
|
|
|
```cpp {.line-numbers}
|
|
|
// 动态开点线段树
|
|
|
#define int long long
|
|
|
#define ls tr[u].l
|
|
|
#define rs tr[u].r
|
|
|
#define mid ((l + r) >> 1)
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int sum, add;
|
|
|
} tr[N << 1];
|
|
|
|
|
|
int root, idx;
|
|
|
// 汇总统计信息
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
|
}
|
|
|
// 创建节点：节点号分配，懒标记初始化
|
|
|
void build(int &u) {
|
|
|
if (u) return;
|
|
|
u = ++idx;
|
|
|
// tr[u].add = 0;
|
|
|
}
|
|
|
|
|
|
void pushdown(int &u, int l, int r) {
|
|
|
if (tr[u].add == 0) return; // 如果没有累加懒标记，返回
|
|
|
build(ls); // 左儿子创建
|
|
|
build(rs); // 右儿子创建
|
|
|
// 懒标记下传
|
|
|
tr[ls].sum += tr[u].add * (mid - l + 1); // 区间和增加=懒标记 乘以 区间长度
|
|
|
tr[rs].sum += tr[u].add * (r - mid);
|
|
|
tr[ls].add += tr[u].add; // 加法的懒标记可以叠加
|
|
|
tr[rs].add += tr[u].add;
|
|
|
// 清除懒标记
|
|
|
tr[u].add = 0;
|
|
|
}
|
|
|
|
|
|
// 区间修改
|
|
|
void modify(int &u, int l, int r, int L, int R, int v) {
|
|
|
build(u); // 动态开点
|
|
|
|
|
|
if (l >= L && r <= R) { // 如果区间被完整覆盖
|
|
|
tr[u].add += v; // 加法的懒标记可以叠加
|
|
|
tr[u].sum += v * (r - l + 1); // 区间和增加=懒标记 乘以 区间长度
|
|
|
return;
|
|
|
}
|
|
|
if (l > R || r < L) return; // 如果没有交集
|
|
|
|
|
|
// 下传懒标记
|
|
|
pushdown(u, l, r);
|
|
|
// 分裂
|
|
|
modify(ls, l, mid, L, R, v), modify(rs, mid + 1, r, L, R, v);
|
|
|
// 汇总
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 区间查询
|
|
|
int query(int u, int l, int r, int L, int R) {
|
|
|
if (l >= L && r <= R) return tr[u].sum; // 如果完整命中，返回我的全部
|
|
|
if (l > R || r < L) return 0; // 如果与我无关,返回0
|
|
|
pushdown(u, l, r);
|
|
|
return query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R);
|
|
|
}
|
|
|
```
|
|
|
|
|
|
递归进入左右儿子，如果要用新点，就开新点。
|
|
|
|
|
|
|
|
|
**$Q1$:如果不动态开点是不是离散化一下就行?**
|
|
|
**答**：理论上可以，但是有的时候强制在线，就不能离散化了
|
|
|
|
|
|
**$Q2$:为什么一定要传递引用呢？不传递引用为什么出错呢？**
|
|
|
**答**：这是因为你向下传递$ls$时，其实$ls$可能还没创建，如果按$\&$地址传递$u$,那么一旦$ls$被创建新节点号时，会回写$tr[u].l$,建立起链条式关系。
|
|
|
如果你不用$\&$地址符传递$u$,那么即使 $ls$被成功创建了新的节点号，但是不知道是谁的左儿子，也就没法回写$tr[u].l$,无法建立起链条关系。
|
|
|
|
|
|
### 练习题
|
|
|
|
|
|
#### [$P3372$ 【模板】线段树$1$](https://www.cnblogs.com/littlehb/p/16224904.html)
|
|
|
**【黄海总结的最为完整的线段树+懒标记，动态开点线段树+懒标记的模板，十分经典，强烈推荐】**
|
|
|
打磨一个模板完美后，开始对以前做过的习题全面修改一遍，$OI$这东西太耗时间了。
|
|
|
|
|
|
#### [$CF915E$ $Physical$ $Education$ $Lessons$](https://www.cnblogs.com/littlehb/p/17664882.html)
|
|
|
|
|
|
#### [$T125847$ 【模板】动态开点线段树](https://www.cnblogs.com/littlehb/p/17667050.html)
|
|
|
**【懒标记线段树，动态+静态线段树实现】**
|
|
|
|
|
|
#### [$P3373$【模板】线段树$2$](https://www.cnblogs.com/littlehb/p/17665847.html)
|
|
|
**【双懒标记线段树，动态+静态线段树实现】**
|
|
|
|
|
|
|
|
|
P3960 列队（动态开点线段树+主席树，未能理解，待研究）
|
|
|
https://www.cnblogs.com/LawrenceSivan/p/14686207.html
|
|
|
|
|
|
|
