1. 什么是值域线段树值域线段树Value Segment Tree又称权值线段树是一种特殊的线段树数据结构。与普通线段树维护区间上的“值”如区间和、最大值不同值域线段树维护的是“值域”上的统计信息。简单来说普通线段树的节点下标对应原始数组的索引区间而值域线段树的节点下标对应的是数值的范围。它的每个节点代表一个数值区间例如 [0, 100]节点中存储的信息是该数值区间内元素出现的次数或其他统计量如和、最大值等。值域线段树的核心思想是将可能出现的数值范围值域作为线段树维护的“坐标轴”从而高效地支持基于数值的查询与更新操作。2. 核心原理与结构2.1 基本定义假设我们需要处理的值域范围为 [L, R]L 和 R 为整数。我们将这个区间作为线段树的根节点并不断二分直到叶子节点代表单个数值即区间长度为 1。例如值域 [0, 7] 构建的值域线段树结构如下每个节点维护其对应值域区间内元素的出现次数根节点: [0, 7] 左孩子: [0, 3] 右孩子: [4, 7] ... 叶子节点: [0,0], [1,1], ..., [7,7]2.2 节点信息每个节点通常维护以下信息cnt当前值域区间内元素出现的总次数。可选sum当前值域区间内所有元素值的总和用于求区间和等。可选max/min当前值域区间内的最大值/最小值。最基础的应用是统计次数因此下文主要以cnt为例。2.3 与普通线段树的区别对比维度普通线段树值域线段树维护的“坐标”数组下标区间 (索引)数值范围 (值域)叶子节点含义原数组某个位置的值某个特定数值的出现次数典型操作区间求和、区间最值查询第k大、统计某个值域内元素个数空间需求O(n)n为数组长度O(V)V为值域大小可能很大3. 基础操作与实现3.1 建树 (Build)值域线段树通常采用“动态开点”或“离散化静态建树”来应对值域过大的问题。方法一离散化 静态建树将所有可能出现的数值收集起来排序去重得到离散化映射。以离散化后的值域大小建立静态线段树。方法二动态开点仅在需要时创建节点节省空间。以下是动态开点值域线段树的 C 实现框架struct Node { int lch, rch; // 左右孩子编号0表示空 int cnt; // 出现次数 // 可扩展 sum, max 等 } tree[MAX_NODES]; int root, tot; // 根节点编号节点总数 // 初始化 void init() { root tot; // 通常根节点对应整个值域 [minVal, maxVal] } // 单点更新在值 x 的出现次数上增加 delta void update(int p, int l, int r, int x, int delta) { if (!p) p tot; // 动态开点 tree[p].cnt delta; if (l r) return; // 叶子节点 int mid (l r) 1; if (x mid) update(tree[p].lch, l, mid, x, delta); else update(tree[p].rch, mid 1, r, x, delta); } // 查询值域 [ql, qr] 内元素的总出现次数 int query(int p, int l, int r, int ql, int qr) { if (!p || ql r || qr l) return 0; if (ql l r qr) return tree[p].cnt; int mid (l r) 1; return query(tree[p].lch, l, mid, ql, qr) query(tree[p].rch, mid 1, r, ql, qr); }3.2 查询第 k 小/第 k 大这是值域线段树的经典应用。利用节点存储的cnt信息可以在 O(log V) 时间内找到第 k 小的数。// 查询第 k 小的数假设 k 从 1 开始 int kth(int p, int l, int r, int k) { if (l r) return l; // 叶子节点即找到答案 int mid (l r) 1; int leftCnt tree[p].lch ? tree[tree[p].lch].cnt : 0; if (k leftCnt) { return kth(tree[p].lch, l, mid, k); } else { return kth(tree[p].rch, mid 1, r, k - leftCnt); } }同理查询第 k 大时可以先查询总次数 total然后查询第 (total - k 1) 小。4. 典型应用场景4.1 动态排名系统维护一个可动态插入/删除的数字集合支持查询某个数值的排名比它小的数有多少个。查询第 k 小的数。查询某个值的前驱比它小的最大数和后继比它大的最小数。这些问题都可以通过值域线段树在 O(log V) 时间内解决。4.2 区间内第 k 大问题可持久化值域线段树对于静态数组查询区间 [l, r] 内的第 k 大数可以通过可持久化值域线段树主席树实现。其核心是建立 n 个版本的线段树每个版本 i 维护前缀 [1, i] 的数值分布通过版本差分得到任意区间的统计信息。4.3 逆序对计数扩展在求解逆序对问题时除了树状数组值域线段树也可以用于统计每个数字之前比它大/小的数字个数同样支持动态插入。4.4 离线查询与扫描线结合将二维平面上的点或矩形查询问题通过扫描线降维用值域线段树维护另一维上的统计信息。5. 优化与注意事项5.1 离散化当值域很大例如 10^9但实际出现的不同数值较少时必须先离散化将原始值映射到 [1, m] 的连续区间再建立大小为 m 的值域线段树。5.2 动态开点与内存管理动态开点能极大节省空间但需要注意节点数组要开足够大通常操作次数 * logV。如果涉及删除操作可考虑内存回收如将删除的节点编号放入空闲队列。5.3 值域边界与负数处理如果值域包含负数可以通过整体偏移例如加上一个足够大的常数将其映射到非负区间。例如值域 [-10^5, 10^5] 可以偏移为 [0, 2*10^5]。6. 总结值域线段树是一种强大的数据结构它将线段树的区间维护能力应用于“数值”维度特别适合处理与数值分布、排名、第k大相关的查询问题。结合离散化、动态开点、可持久化等技巧可以灵活应对各种数据范围和操作要求。掌握值域线段树是深入理解高级数据结构如主席树、树套树的重要基础。建议从实现一个支持插入、删除、查询第k小的动态集合开始练习再逐步挑战更复杂的应用。