Order Statistic Trees
An order-statistic data structure maintains an ordered collection and answers rank and selection queries: how many values are smaller than x, and what is the K-th smallest stored occurrence? A balanced search tree can augment each node with its subtree size. When the set of possible keys is known in advance, a portable alternative is coordinate compression plus a Fenwick tree of frequencies. This lesson implements that alternative using only standard C++17. It supports duplicates, insertion, deletion of one occurrence, rank, and selection without relying on compiler-specific policy-based containers.
Prerequisites: Fenwick trees, binary search/lower_bound, coordinate compression, binary representation.
Build the idea
Compress order, not arithmetic
Read all commands first and collect values appearing in insertions or deletions. Sort and remove duplicates to obtain keys. Each value's position becomes its 1-based rank. Compression preserves comparisons: x<y exactly when rank(x)<rank(y). It does not preserve gaps or numeric differences. Query thresholds need not be keys: lower_bound finds how many distinct compressed values are strictly below any x.
Store multiplicities
Frequency rank r counts occurrences of keys[r-1]. Fenwick prefix(r) counts all occurrences with compressed rank at most r. Inserting x adds 1; deleting one existing x adds -1. A separate frequency array prevents deletion from making a count negative. Nonnegative counts make prefix totals monotonic, a crucial precondition for the selection search.
Count values smaller than x
Let p=lower_bound(keys,x)-keys.begin(). Exactly p distinct compressed values are below x, so prefix(p) counts their occurrences. Duplicates are counted individually. For multiset [2,5,5,9], COUNT 5 is 1, COUNT 6 is 3, and COUNT 1 is 0. No key is inserted by this query.
Select without repeated binary search
To find K-th, locate the smallest rank with prefix(rank)≥K. Start idx=0 and try Fenwick steps from the highest power of two downwards. If candidate=idx+step is in bounds and bit[candidate]<K, skip that whole block: subtract its count from K and move idx to candidate. The maintained skipped prefix contains fewer than the original K occurrences. At the end idx+1 is the required rank. This uses O(log m) steps, avoiding an O(log²m) outer binary search.
Example and alternatives
Insert 5,2,5,9. KTH 3 is 5, COUNT 5 is 1. Delete one 5, leaving [2,5,9]; KTH 3 becomes 9. Invalid K returns NONE. A segment tree of frequencies can implement the same selection by descending according to left-subtree counts. If genuinely new keys arrive online and cannot be pre-read, use an augmented balanced BST or a dynamic segment tree with a known numeric domain. The offline compression restriction is a deliberate design choice.
An empty multiset is valid
With no insertions, every COUNT returns zero and every KTH returns NONE. If no update key exists, the Fenwick array has size zero; the validity check prevents selection from being called. Absence is an ordinary state, not a special numeric key.
C++17 implementation
This is a complete program. Compile with C++17 and enter the input described below.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
struct Command{
string op;
long long x;
};
struct Fenwick{
int n;
vector<int>bit;
explicit Fenwick(int n):n(n),bit(n+1){
}
void add(int i,int d){
for(;i<=n;i+=i&-i){
bit[i]+=d;
}
}
int prefix(int i)const{
int s=0;
for(;i>0;i-=i&-i){
s+=bit[i];
}
return s;
}
int kth(int k)const{ // Requires 1 <= k <= total and nonnegative frequencies.
// idx is a skipped prefix with fewer than the original k occurrences.
int idx=0,step=1;
while(step<=n/2){
step*=2;
}
for(;step;step/=2){
int next=idx+step;
// Skip this Fenwick block only when the answer lies beyond it.
if(next<=n&&bit[next]<k){
idx=next;
k-=bit[next];
}
}
return idx+1;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin>>q;
vector<Command>cmd(q);
vector<long long>keys;
for(auto&c:cmd){
cin>>c.op>>c.x;
if(c.op=="ADD"||c.op=="DEL"){
keys.push_back(c.x);
}
}
// Compression preserves ordering; frequencies keep duplicate occurrences.
sort(keys.begin(),keys.end());
keys.erase(unique(keys.begin(),keys.end()),keys.end());
Fenwick fw((int)keys.size());
vector<int>freq(keys.size()+1);
int total=0;
for(const auto&c:cmd){
int p=(int)(lower_bound(keys.begin(),keys.end(),c.x)-keys.begin());
// lower_bound gives the number of distinct keys strictly below x.
if(c.op=="COUNT"){
cout<<fw.prefix(p)<<'\n';
}
else if(c.op=="KTH"){
if(c.x<1||c.x>total){
cout<<"NONE\n";
}
else{
cout<<keys[fw.kth((int)c.x)-1]<<'\n';
}
}
else if(c.op=="ADD"){
freq[p+1]++;
fw.add(p+1,1);
total++;
}
// Ignore absent deletions so prefix frequencies stay nonnegative.
else if(freq[p+1]>0){
freq[p+1]--;
fw.add(p+1,-1);
total--;
}
}
}
Complexity analysis
For q commands and m distinct update keys: compression O(q log q) time, O(q+m) storage including offline commands. Each insert, delete, count, or K-th query takes O(log(m+1)); K-th uses Fenwick binary lifting. Frequencies and total fit int when q does.
Example input and output
q commands: ADD x inserts one occurrence, DEL x removes one if present, COUNT x counts occurrences strictly below x, KTH k selects a 1-based occurrence or prints NONE. Keys fit long long; q fits int.
Input
9 ADD 5 ADD 2 ADD 5 ADD 9 KTH 3 COUNT 5 DEL 5 KTH 3 KTH 4
Output
5 1 9 NONE
Selection counts duplicate 5s separately. Removing one leaves [2,5,9]. A fourth occurrence then does not exist.
Practical applications
Dynamic medians; rank queries; selecting the K-th available position; inversion statistics; frequency-based order queries. Related structures include augmented balanced BSTs and frequency segment trees.
Check your understanding
Why must frequencies remain nonnegative?
Put it into practice
Print the lower median after every update, or EMPTY when there are no values.
Show a hint
For total>0, select K=(total+1)/2.