Core Logic and Mathematical Principles
Traditional segment trees maintain the index range of the original array at their leaf nodes (e.g., the $i^{th}$ element), while Value Segment Trees maintain the value range of the data at their leaf nodes. The core logic is: treat the segment tree as a bucket array, where each leaf node $[v, v]$ records the frequency (Count) of the value $v$ appearing in the sequence.
1. Spatial Topology and Mathematical Mapping
Let the value range closed interval represented by the current node $u$ be $[L, R]$, and its core state tree[u] represents: the total count of elements within the range $[L, R]$ in the entire sequence.
- Divide and Conquer Midpoint: $M = (L + R) ext{ >> } 1$.
- The left subtree maintains the frequency sum of the value range $[L, M]$; the right subtree maintains the frequency sum of the value range $[M + 1, R]$.
- Algebraic Relation: $tree[u] = tree[u ext{ << } 1] + tree[u ext{ << } 1 | 1]$.
2. Proof of Binary Search on Dynamic Ranking Tree
The most hardcore application of the Value Segment Tree is that it can query the global $K^{th}$ smallest number online in logarithmic complexity $O( ext{log} U)$ (where $U$ is the size of the value range). Proof: Given that the left subtree represents a value range with a total of $count_{left} = tree[u ext{ << } 1]$ numbers.
- If $K ext{ <= } count_{left}$: This indicates that all of the $count_{left}$ smallest numbers in the entire sequence are within the left value range, and the target $K^{th}$ smallest number must fall within the value range of the left subtree.
- If $K > count_{left}$: This indicates that the total count of numbers in the left value range is not enough for $K$. The target number must fall within the value range of the right subtree. At this point, we enter the right subtree, and since we have excluded $count_{left}$ numbers from the left value range, the target ranking in the right subtree needs to be adjusted to $K - count_{left}$.
State Design and Algorithm Derivation
When the value range is too large, the Value Segment Tree must combine with the dynamic opening mechanism from Section 7.1. This section takes the dynamic opening Value Segment Tree as an example to derive the core operations of the ranking tree:
1. Insert Value (Insert)
Define the recursive function insert(u, l, r, val). Locate along the value range by binary division. Each time a node is traversed, it indicates that the value range of that node contains val, executing:
$$tree[u] = tree[u] + 1$$
The process stops when it reaches a leaf node (where $l = r = val$). The deletion of a value follows the same logic, changing $+1$ to $-1$.
2. Query Global $K^{th}$ Smallest (Query_Kth)
Define the recursive function query_kth(u, l, r, k):
- If $l = r$, it indicates that the value range has converged to an isolated point, return $l$ directly.
- Calculate the frequency of the left subtree: $cnt_{left} = tree[ls[u]]$.
- Conditional branches:
- If $k ext{ <= } cnt_{left}$:
return query_kth(ls[u], l, m, k). - If $k > cnt_{left}$:
return query_kth(rs[u], m + 1, r, k - cnt_{left}).
3. Query the Ranking of Value val (Query_Rank)
This means finding out how many numbers are strictly less than val in the sequence, with the final rank being number of elements found + 1. Define the recursive function query_rank(u, l, r, val):
If the queried value range is completely less than the current interval, or if the current node is null, return 0.
If $val > m$, it indicates that the entire left subtree value range $[l, m]$ is strictly less than val, directly adding the total frequency of the left subtree tree[ls[u]] and recursively querying the right subtree:
$$ ext{Rank} = tree[ls[u]] + ext{query extunderscore rank}(rs[u], m + 1, r, val)$$
If $val ext{ <= } m$, it indicates that the entire right subtree is greater than or equal to val, contributing nothing to the ranking, and we directly recurse into the left subtree.
C++ Standard Source Code (NOIP Style)
#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;
}
// Value range U = 10^9, number of operations Q = 10^5.
// Each insertion/deletion generates about log2(U) 30 nodes. Space allocation 100000 * 30 = 3 * 10^6
const int MAX_NODES = 3000005;
const int INF = 1000000000; // Assume data value range is [1, 10^9]
int root = 0, cnt = 0;
int tree[MAX_NODES]; // Store frequency sums within the value range
int ls[MAX_NODES];
int rs[MAX_NODES];
inline void pushup(int u) {
tree[u] = tree[ls[u]] + tree[rs[u]];
}
// Core operation: Insert/Delete elements. val_cnt of 1 represents insertion, -1 represents deletion
void update(int &u, int l, int r, int val, int val_cnt) {
if (!u) u = ++cnt;
if (l == r) {
tree[u] += val_cnt; // Critical pitfall: frequency modification must be accumulative, cannot be forced to assign
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);
}
// Core operation: Query global $K^{th}$ smallest
int query_kth(int u, int l, int r, int k) {
if (l == r) return l; // Successfully converged to the target value
int m = (l + r) >> 1;
int left_cnt = tree[ls[u]]; // Null pointer ls[u]=0 corresponds to tree[0]=0, logically self-consistent
if (k <= left_cnt) {
return query_kth(ls[u], l, m, k);
} else {
return query_kth(rs[u], m + 1, r, k - left_cnt); // Critical pitfall: switching to the right subtree must subtract the left subtree's frequency contribution
}
}
// Core operation: Query ranking of val (strictly less than val's element count + 1)
int query_rank(int u, int l, int r, int val) {
if (!u) return 0;
if (l == r) return 0; // Reached leaf means no smaller
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); // Insert x
} else if (opt == 2) {
update(root, 1, INF, x, -1); // Delete x
} else if (opt == 3) {
printf("%d\n", query_rank(root, 1, INF, x) + 1); // Output ranking
} else if (opt == 4) {
printf("%d\n", query_kth(root, 1, INF, x)); // Output the x-th smallest number
}
}
return 0;
}NOIP Practical Pitfall Guide
1. Forgetting to Adjust Ranking $K$ When Switching to the Right Subtree
In executing query_kth when preparing to enter the right subtree, the incorrect approach is query_kth(rs[u], m + 1, r, k). Since there are already left_cnt numbers in the left subtree that are smaller than the value range of the right subtree, if this count is not excluded (i.e., changed to k - left_cnt), the ranking standard will severely shift upwards during the binary decision in the right subtree, leading to incorrect results.
2. Neglected Translation Mapping for Negative Value Ranges
Many problems provide value ranges that include negative numbers (e.g., $[-10^9, 10^9]$). Since the endpoints $L, R$ of the Value Segment Tree are logically treated as array index mappings or binary boundaries, directly substituting negative numbers into int m = (l + r) >> 1 may cause mathematical uncertainty in C++ due to integer division (e.g., -1 >> 1 may not equal -1 in older standards). The most prudent engineering solution is to uniformly add a large constant (e.g., $+10^9$) to all input data, shifting the entire range to positive integers within $[1, 2 imes 10^9]$.
Classic NOIP/Luogu Problems
1. Luogu P3369 [Template] Ordinary Balanced Tree (Value Segment Tree Over Balanced Tree Version)
- Problem Description: Maintain a dynamic set supporting insertion, deletion, querying the ranking of $X$, querying the number with ranking $K$, and finding the predecessor and successor of $X$.
- Essence of the Problem: Ranking retrieval on value ranges.
- Core Problem-Solving Idea: The classic solution for this problem is Treap or Splay, but using a dynamic opening Value Segment Tree can yield hacker-level concise code without rotations or pointer crashes. Insertions, deletions, querying rankings, and querying the $K^{th}$ smallest are as shown in the source code.
- Finding Predecessor (the largest number less than $X$): First find the ranking $R$ of $X$, then query the global $R-1^{th}$ smallest number.
- Finding Successor (the smallest number greater than $X$): First find the ranking $R$ of $X+1$, then query the global $R^{th}$ smallest number. All operations strictly have a time complexity locked at $O( ext{log} U)$.
2. Luogu P6160 [CERC2013] Insights / Dynamic Median Maintenance
- Problem Description: Dynamically read an ever-growing stream of integers, requiring real-time output of the current median of the set after each number is read in.
- Essence of the Problem: Fixed-point retrieval using the Value Segment Tree.
- Core Problem-Solving Idea: Use the Value Segment Tree to maintain the frequency of the set. Let the total count of valid elements in the current set be $N$.
- If $N$ is odd, the median is the global $ rac{N+1}{2}^{th}$ smallest number.
- If $N$ is even, the median is usually defined as the average of the $ rac{N}{2}^{th}$ smallest and $ rac{N}{2} + 1^{th}$ smallest numbers.
Using
query_kthcan achieve pinpoint efficiency in $O( ext{log} U)$ time for each query, far surpassing the double-heap maintenance scheme.