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) / 2$.
- 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 * 2] + tree[u * 2 + 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(\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 * 2]$ numbers.
- If $K \leq 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. 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[u * 2]$.
- Conditional branches:
- If $k \leq cnt_{left}$:
return query_kth(u * 2, l, m, k). - If $k > cnt_{left}$:
return query_kth(u * 2 + 1, 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[u * 2] and recursively querying the right subtree:
$$Rank = tree[u * 2] + query\_rank(u * 2 + 1, m + 1, r, val)$$
If $val \leq 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 * 8 + x * 2) + (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) / 2;
if (val <= m) update(ls[u], l, m, val, val_cnt);
else update(rs[u], m + 1, r, val, val