权值线段树的动态构建与合并技术
权值线段树基础
权值线段树是一种以数值范围为索引的线段树结构，其节点维护的是特定值域内元素出现频次等信息。与普通线段树按位置划分不同，权值线段树按数值大小划分区间。
例如，在值域范围 $1 \leq a_i \leq 8$ 时，可构建如下结构：
传统建树方式的空间复杂度为 $O(A \log A)$，当值域扩展至 $10^9$ 量级时，内存开销将急剧上升，难以承受。
动态开点优化
为解决空间浪费问题，引入动态开点机制：初始时不预分配所有节点，仅在实际需要时才创建对应节点。
核心思想是通过指针式存储（如数组下标模拟指针）实现按需生成节点。当访问一个未初始化的子节点时，立即为其分配新编号并递归建立子树。
该方法的空间复杂度降至 $O(n \log A)$，且通常远低于理论上限。
代码实现
int ls[maxn], rs[maxn], val[maxn], cnt, rt;
// ls:左子节点编号, rs:右子节点编号, val:当前节点维护值, cnt:当前使用节点数, rt:根节点编号
void update(int &x, int l, int r, int pos, int k) {
if (!x) x = ++cnt; // 若节点不存在，则新建
if (l == r) {
val[x] += k; // 更新计数
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(ls[x], l, mid, pos, k);
else
update(rs[x], mid + 1, r, pos, k);
// 合并子节点信息
val[x] = val[ls[x]] + val[rs[x]];
}
关键在于 `if (!x) x = ++cnt;` 这一行：它确保了只有真正被访问的路径才会生成节点。由于每个插入操作最多影响 $\log A$ 层节点，因此整体空间可控。
线段树合并
当多个独立的动态开点线段树需合并为一个整体时，可采用递归合并策略：
- 若两棵树在某节点均为空，结果也为空；
- 若仅一棵树存在，直接返回该树的根；
- 若两棵树均存在，则合并其维护的信息，并递归处理左右子树。
合并逻辑适用于维护频次、最大值等聚合信息的场景。时间复杂度取决于重叠节点数量，最坏情况为 $O(\text{公共节点数} \times \text{合并代价})$。
合并实现
int merge(int x1, int x2, int l, int r) {
if (!x1) return x2;
if (!x2) return x1;
if (l == r) {
val[x1] += val[x2];
return x1;
}
int mid = (l + r) >> 1;
ls[x1] = merge(ls[x1], ls[x2], l, mid);
rs[x1] = merge(rs[x1], rs[x2], mid + 1, r);
val[x1] = val[ls[x1]] + val[rs[x1]];
return x1;
}
典型应用案例
CF600E Lomsat Gelral —— 树上颜色统计
给定一棵有根树，每个节点有颜色。要求对每个节点，输出其子树中出现频率最高的颜色编号之和。
解法：为每个节点维护一个动态开点权值线段树，记录各颜色出现次数。自底向上合并子树线段树，并加入自身颜色，最终查询最大频次对应的总和。
洛谷P4556 —— 树上路径标签统计
支持对树上路径进行"打标签"操作，求每个节点最终出现最多的标签。
解法：结合树上差分与线段树合并。对每条路径 $(x,y)$ 打标签 $z$，执行：在 $x$、$y$ 处加一，在 $LCA(x,y)$ 及其父节点处减一。最后通过合并子树线段树得出答案。
洛谷P3224 —— 永无乡 —— 动态连通性第k小查询
维护若干点的连通块，支持连边与查询某连通块中权值第 $k$ 小的点。
解法：使用并查集管理连通关系，每个连通块维护一个权值线段树。每次合并连通块即合并对应的线段树。查询时在根节点的线段树中查找第 $k$ 小值。
