前言
我是一个什么什么傻卵啊啊啊啊啊啊啊啊，连线段树合并都学不明白qaq
正文
权值线段树
含义：
是用来维护好多好多桶的线段树. 桶是一个用来计数的东西.
与普通线段树的区别
普通线段树是用来维护区间和、积、最值等一系列的东西.
权值线段树是用来维护某个区间内的数出现了多少次的。它还可以插入数据，维护第 \(k\) 小(大)值.
动态开点
有时候题目给的数据范围很大，用普通的线段树可能会MLE时，我们就会选择动态开点。动态开点，就是什么时候需要某个点，什么时候把它建出来。所以动态开点线段树的编号法则不符合普通线段树的“父子二倍法”。我们选择用一个非常普通的计数变量(例如 \(cnt\) )来表示线段树的节点编号.
代码实现
void insert(int& p, int l, int r, int x, int v) {
// p是节点编号, 要引用传参, [l, r]是值域, x ∈ [l, r], v是增量.
if (!p) p = ++cnt; // 如果不存在这个节点, 就把这个节点开出来.
if (l == r) { // 递归到叶子结点.
t[p].data += v;
return;
}
int mid = (l + r) >> 1;
// 判断x在哪一半区间内
if (x <= mid) insert(t[p].l, l, mid, x, v);
else insert(t[p].r, mid + 1, r, x, v);
pushup(p);
}
线段树合并
就是把若干棵线段树合并到一起. 合并操作是求和(积)还是求最值取决于个人需要.
合并的两棵线段树的大的值域应当是相同的.
如何合并
- 先递归到叶子结点.
- 若两棵线段树的相同位置都存在节点, 则合并两个节点作为新的节点.
- 若某一刻线段树的相应节点不存在, 则取那个存在的节点作为新的节点.
代码实现
void merge(int& a, int b, int l, int r) {
// a需要引用传参, 因为将b合并到a上.
if (!a || !b) {
a = a ? a : b;
return;
}
if (l == r) {
t[a].data += t[b].data;
// 这里是对值的合并操作. 这里以两棵线段树求和为例.
return;
}
int mid = (l + r) >> 1;
// 左子树和左子树合并, 右子树和右子树合并.
merge(t[a].l, t[b].l, l, mid);
merge(t[a].r, t[b].r, mid + 1, r);
pushup(a);
}
\[TO BE CONTINUED......
\]