深入解析权值线段树：动态名次与高效查询

核心逻辑与数学原理

传统线段树的叶子节点维护的是原数组的下标区间（如第 $i$ 个元素），而权值线段树（Value Segment Tree）的叶子节点维护的是数据的值域区间。其核心逻辑是：将线段树视作一个桶数组，每个叶子节点 $[v, v]$ 记录数值 $v$ 在序列中出现的频次（Count）。

1. 空间拓扑与数学映射

设当前节点 $u$ 代表的值域闭区间为 $[L, R]$，其维护的核心状态 tree[u] 代表：整个序列中，大小在 $[L, R]$ 范围内的元素个数总和。

分治中点：$M = (L + R) ext{ >> } 1$。
左子树维护值域 $[L, M]$ 的频次和；右子树维护值域 $[M + 1, R]$ 的频次和。
代数关系：$tree[u] = tree[u ext{ << } 1] + tree[u ext{ << } 1 | 1]$。

2. 动态名次树的树上二分证明

权值线段树最硬核的应用是可以在 $O( ext{log} U)$ 的对数复杂度内（$U$ 为值域大小）在线查询全局第 $K$ 小的数。证明：已知左子树代表的值域区间内一共有 $count_{left} = tree[u ext{ << } 1]$ 个数。

若 $K ext{ <= } count_{left}$：说明整个序列中前 $count_{left}$ 小的数都在左值域内，目标第 $K$ 小的数必然落在左子树的值域区间中。
若 $K > count_{left}$：说明左值域内的所有数加起来都不够 $K$ 个。目标数必然落在右子树的值域区间内。此时进入右子树，由于排除了左值域的 $count_{left}$ 个数，目标排名在右子树中需要修正为 $K - count_{left}$。

状态设计与算法推导

在值域过大时，权值线段树必须结合 7.1 节的动态开点机制。本节以动态开点权值线段树为例，推导名次树核心操作：

1. 插入数值（Insert）

定义递归函数 insert(u, l, r, val)。沿着值域二分定位。每经过一个节点，说明该节点的值域区间包含了 val，执行：

$$tree[u] = tree[u] + 1$$

最终触及叶子节点（$l = r = val$）时停止。删除数值同理，将 $+1$ 改为 $-1$。

2. 查询全局第 $K$ 小（Query_Kth）

定义递归函数 query_kth(u, l, r, k)：

若 $l = r$，说明值域区间收敛到一个孤立点，直接返回 $l$。
计算左子树拥有的频次：$cnt_{left} = tree[ls[u]]$。
条件判定分支：

若 $k ext{ <= } cnt_{left}$：return query_kth(ls[u], l, m, k)。
若 $k > cnt_{left}$：return query_kth(rs[u], m + 1, r, k - cnt_{left})。

3. 查询数值 `val` 的名次（Query_Rank）

即求序列中有多少个数严格小于 val，最终名次为 求得个数 + 1。定义递归函数 query_rank(u, l, r, val)：若查询的值域完全小于当前区间，或者当前节点为空，返回 0。若 $val > m$，说明左子树值域 $[l, m]$ 全体严格小于 val，直接累加左子树总频次 tree[ls[u]]，并递归右子树：

$$ ext{Rank} = tree[ls[u]] + ext{query extunderscore rank}(rs[u], m + 1, r, val)$$

若 $val ext{ <= } m$，说明右子树全体大于等于 val，对排名无贡献，直接递归左子树。

C++ 标准源码（NOIP风格）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

// 值域 U = 10^9，操作数 Q = 10^5。
// 每次插入/删除产生 log2(U) 约 30 个节点。空间开辟 100000 * 30 = 3 * 10^6
const int MAX_NODES = 3000005;
const int INF = 1000000000; // 假设数据值域在 [1, 10^9]

int root = 0, cnt = 0;
int tree[MAX_NODES]; // 存储值域区间内的频次和
int ls[MAX_NODES];
int rs[MAX_NODES];

inline void pushup(int u) {
    tree[u] = tree[ls[u]] + tree[rs[u]];
}

// 核心操作：插入/删除元素。val_cnt 为 1 代表插入，-1 代表删除
void update(int &u, int l, int r, int val, int val_cnt) {
    if (!u) u = ++cnt;
    if (l == r) {
        tree[u] += val_cnt; // 致命踩坑点：频次修改必须可累加，不能直接强行赋值
        return;
    }
    int m = (l + r) >> 1;
    if (val <= m) update(ls[u], l, m, val, val_cnt);
    else update(rs[u], m + 1, r, val, val_cnt);
    pushup(u);
}

// 核心操作：查询全局第 K 小
int query_kth(int u, int l, int r, int k) {
    if (l == r) return l; // 成功收敛至目标数值
    int m = (l + r) >> 1;
    int left_cnt = tree[ls[u]]; // 空指针 ls[u]=0 对应 tree[0]=0，逻辑自洽
    if (k <= left_cnt) {
        return query_kth(ls[u], l, m, k);
    } else {
        return query_kth(rs[u], m + 1, r, k - left_cnt); // 致命踩坑点：转向右子树必须减去左子树的频次贡献
    }
}

// 核心操作：查询 val 的排名（严格小于 val 的元素个数 + 1）
int query_rank(int u, int l, int r, int val) {
    if (!u) return 0;
    if (l == r) return 0; // 触及叶子说明没有更小的
    int m = (l + r) >> 1;
    if (val <= m) {
        return query_rank(ls[u], l, m, val);
    } else {
        return tree[ls[u]] + query_rank(rs[u], m + 1, r, val);
    }
}

int main() {
    int q = read();
    while (q--) {
        int opt = read();
        int x = read();
        if (opt == 1) {
            update(root, 1, INF, x, 1); // 插入 x
        } else if (opt == 2) {
            update(root, 1, INF, x, -1); // 删除 x
        } else if (opt == 3) {
            printf("%d\n", query_rank(root, 1, INF, x) + 1); // 输出排名
        } else if (opt == 4) {
            printf("%d\n", query_kth(root, 1, INF, x)); // 输出第 x 小的数
        }
    }
    return 0;
}

NOIP 实战避坑指南

1. 转向右子树时忘记消减排名 $K$

在执行 query_kth 准备进入右子树时，错误的写法是 query_kth(rs[u], m + 1, r, k)。因为左子树中已经存在了 left_cnt 个比右子树值域还要小的数，如果不把这部分数量剔除（即改为 k - left_cnt），在右子树进行二分判定时，排名标准就会发生向高位的严重偏移，直接导致返回错误结果。

2. 负数值域未做平移映射处理

很多题目给定的值域包含负数（如 $[-10^9, 10^9]$）。由于权值线段树的区间端点 $L, R$ 在逻辑上通常作为数组下标的映射或二分边界，直接将负数代入 int m = (l + r) >> 1 会引发 C++ 向零取整的底层的数学不确定性（如 -1 >> 1 在旧标准中可能不为 -1）。最稳妥的工程解法是：将所有输入的数据统一加上一个大常数（如 $+10^9$），整体平移映射到正整数域 $[1, 2 imes 10^9]$ 内部进行维护。

经典 NOIP/洛谷真题

1. 洛谷 P3369 【模板】普通平衡树（权值线段树过平衡树版）

题意描述：维护一个动态集合，支持插入、删除、查询 $X$ 的排名、查询排名为 $K$ 的数、求 $X$ 的前驱与后继。
问题本质：值域上的名次检索。
核心解题思路：该题经典解法是 Treap 或 Splay，但用动态开点权值线段树可以写出无旋转、无位针崩溃的黑客级洗练代码。插入、删除、求排名、求第 $K$ 小如源码所示。
求前驱（小于 $X$ 的最大数）：先求出 $X$ 的排名 $R$，然后查询全局第 $R-1$ 小的数。
求后继（大于 $X$ 的最小数）：先求出 $X+1$ 的排名 $R$，然后查询全局第 $R$ 小的数。所有操作时间复杂度严格锁死在 $O( ext{log} U)$。

2. 洛谷 P6160 [CERC2013] Insights / 动态中位数维护

题意描述：动态读入一个不断增长的整数流，每读入一个数，要求实时输出当前集合的中位数。
问题本质：权值线段树定点检索。
核心解题思路：使用权值线段树维护集合频次。设当前集合内的总有效元素个数为 $N$。
若 $N$ 为奇数，中位数即为全局第 $rac{N+1}{2}$ 小的数。
若 $N$ 为偶数，中位数通常定义为第 $rac{N}{2}$ 小与第 $rac{N}{2} + 1$ 小的数的均值。利用 query_kth 可以在 $O( ext{log} U)$ 时间内定点秒杀每次询问，效率远超双堆维护方案。