Introduction

P3369 [Template] Ordinary Balanced Tree is a classic data-structure template problem. The usual solutions use a Treap, Splay tree, fhq Treap, or pbds.

This article records an unconventional implementation: maintaining an ordered multiset with a binary trie (01Trie).
As long as the value domain is manageable, all six operations required by the problem:

• Insertion
• Deletion
• Rank queries
• Finding the $k$th smallest element
• Predecessor queries
• Successor queries

can be implemented using counts stored in the trie.

1. What the Problem Really Requires

We need to maintain a multiset that supports order statistics.
The problem does not inherently require a “balanced tree”; it requires us to maintain:

1. The ordering of the elements in the collection.
2. How many elements precede a given value.
3. Which value corresponds to a given rank.

If a binary trie tracks “how many elements pass through each node,” it can support these operations.

2. The Core Idea

A binary trie is built from the most significant bit down to the least significant bit:

• The left child represents a 0 at the current bit.
• The right child represents a 1 at the current bit.

When the higher-bit prefix is the same:

Every number in the left subtree is smaller than every number in the right subtree.

The trie therefore has a form of “local ordering.”
If we also track how many elements pass through each node, we can support the same operations as an order-statistic tree:

• Count elements strictly smaller than a given value.
• Find the $k$th smallest element.

Predecessors and successors can then be derived from these two operations.

3. Shifting the Value Domain

The code uses:

1

const int offset = 1e7;

Every input value is shifted to:

1

x + offset

This maps any potentially negative values into a nonnegative range, making it convenient to maintain them in the trie using ordinary binary representations.

If the original range is:

then the shifted range is:

Subtract offset when outputting an answer to recover the original value.

4. Choosing the Bit Width

The code iterates over bits as follows:

1

for (int i = 25; i >= 0; --i)

The maximum shifted value is approximately $2\times 10^7$, and:

• $2^{24}=16777216$
• $2^{25}=33554432$

Thus, using bits 25 through 0, for a total of 26 bits, is sufficient to cover all possible values.

5. The Information We Maintain

The core arrays are:

1

int trie[maxn][2], cnt[maxn];

Their meanings are:

• trie[p][0]: the 0-child of node p.
• trie[p][1]: the 1-child of node p.
• cnt[p]: the number of elements passing through node p.

We can interpret cnt[p] as:
The total number of elements in the subtree rooted at this node that pass through this prefix.

Since every number follows a full path of exactly 26 levels, no separate terminal marker is needed.

6. Insertion and Deletion

1. Insertion

1
2
3
4
5
6
7
8
9
10
11

void Insert(int x) {
    int p = 0;
    for (int i = 25; i >= 0; --i) {
        int v = x >> i & 1;
        if (!trie[p][v]) {
            trie[p][v] = ++idx;
        }
        p = trie[p][v];
        cnt[p]++;
    }
}

Extract each bit from highest to lowest:

• Create the corresponding child if it does not exist.
• Follow the path downward.
• Increment the count of each node visited.

After insertion, the counts of all nodes along the path for x are correctly maintained.

2. Deletion

1
2
3
4
5
6
7
8

void Delete(int x) {
    int p = 0;
    for (int i = 25; i >= 0; --i) {
        int v = x >> i & 1;
        p = trie[p][v];
        cnt[p]--;
    }
}

For deletion, follow the original path and decrement cnt at each node.
There is no need to physically remove nodes; keeping the counts correct is enough.

This implementation assumes that the problem guarantees valid deletions: the element to be deleted is present.

7. Rank Queries: getRank

The code is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int getRank(int x) {
    int p = 0, rank = 0;
    for (int i = 25; i >= 0; --i) {
        int v = x >> i & 1;
        if (v) {
            rank += cnt[trie[p][0]];
        }
        p = trie[p][v];
        if (!p) {
            break;
        }
    }
    return rank;
}

This function returns something different from the “rank” defined in the statement:

The number of elements strictly smaller than x.

The main function therefore outputs the following for a rank query:

1

getRank(x + offset) + 1

Correctness Analysis

Consider the current bit, working from highest to lowest.

Let its value be v:

When v = 0

Any number with a 1 at the current bit and the same higher-bit prefix must be greater than x.
It therefore contributes nothing to the count of elements smaller than x. Continue directly along the 0-branch.

When v = 1

Every number with the same higher-bit prefix as x but a 0 at the current bit must be strictly smaller than x.
We can therefore add the whole count directly:

1

rank += cnt[trie[p][0]];

Then continue down the 1-branch to count the remaining possibilities.

Early Exit

If p becomes 0 at any step, the current prefix does not exist. No lower bits can contribute anything further, so we can stop immediately.

8. Finding the $k$th Smallest Element: getVal

The code is:

1
2
3
4
5
6
7
8
9
10
11
12
13

int getVal(int x) {
    int p = 0, val = 0;
    for (int i = 25; i >= 0; --i) {
        if (cnt[trie[p][0]] >= x) {
            p = trie[p][0];
        } else {
            x -= cnt[trie[p][0]];
            p = trie[p][1];
            val |= 1 << i;
        }
    }
    return val;
}

This function returns the xth smallest element in the current collection, with x being 1-based.

Correctness Analysis

At any trie node:

• The left subtree has a 0 at the current bit.
• The right subtree has a 1 at the current bit.

Since 0 < 1 at the current bit, every element in the left subtree is smaller than every element in the right subtree.

Therefore:

• If the left subtree has at least x elements, the xth smallest must be in that subtree.
• Otherwise, it must be in the right subtree, and we subtract the number of elements in the left subtree from x.

When moving into the right subtree, set the current bit to 1:

1

val |= 1 << i;

This eventually constructs the complete value.

9. Predecessors and Successors

1. Predecessor

1
2
3

int getPrev(int x) {
    return getVal(getRank(x));
}

The predecessor is defined as “the greatest value strictly smaller than x.”

If there are k elements strictly smaller than x, the largest of those is exactly the kth smallest element. Thus:

2. Successor

1
2
3

int getNext(int x) {
    return getVal(getRank(x + 1) + 1);
}

The successor is defined as “the smallest value strictly greater than x.”

Since getRank(y) returns the number of elements strictly smaller than y:

Therefore:

1

getRank(x + 1)

is the number of elements in the collection that are less than or equal to x.

The rank of the smallest element strictly greater than x is then:

1

getRank(x + 1) + 1

Use getVal to retrieve the corresponding value.

10. Mapping Operations in the Main Function

1
2
3
4
5
6
7
8
9
10
11
12
13

if (op == 1) {
    Insert(x + offset);
} else if (op == 2) {
    Delete(x + offset);
} else if (op == 3) {
    cout << getRank(x + offset) + 1 << '\n';
} else if (op == 4) {
    cout << getVal(x) - offset << '\n';
} else if (op == 5) {
    cout << getPrev(x + offset) - offset << '\n';
} else {
    cout << getNext(x + offset) - offset << '\n';
}

The operations mean:

• 1 x: Insert x.
• 2 x: Delete one occurrence of x.
• 3 x: Query the rank of x.
• 4 x: Query the xth smallest value.
• 5 x: Query the predecessor of x.
• 6 x: Query the successor of x.

Since the trie stores shifted values, subtract offset whenever outputting an actual value.

11. Complexity Analysis

Let the size of the value domain be $V$.

Every operation only needs to follow the trie from the highest bit to the lowest. The time complexities are therefore:

• Insertion: $O(\log V)$
• Deletion: $O(\log V)$
• Rank query: $O(\log V)$
• $k$th-smallest query: $O(\log V)$
• Predecessor query: $O(\log V)$
• Successor query: $O(\log V)$

Here, the value domain uses a fixed width of 26 bits, giving each operation a small constant factor.

For space complexity, inserting a new number may create 26 nodes in the worst case.
For around $10^5$ operations, we need approximately:

nodes, so the code defines:

1

const int maxn = 2.6e6;

12. Complete Code and Submission Record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2.6e6, offset = 1e7;

int n, idx, trie[maxn][2], cnt[maxn];

void Insert(int x) {
    int p = 0;
    for (int i = 25; i >= 0; --i) {
        int v = x >> i & 1;
        if (!trie[p][v]) {
            trie[p][v] = ++idx;
        }
        p = trie[p][v];
        cnt[p]++;
    }
}

void Delete(int x) {
    int p = 0;
    for (int i = 25; i >= 0; --i) {
        int v = x >> i & 1;
        p = trie[p][v];
        cnt[p]--;
    }
}

int getRank(int x) {
    int p = 0, rank = 0;
    for (int i = 25; i >= 0; --i) {
        int v = x >> i & 1;
        if (v) {
            rank += cnt[trie[p][0]];
        }
        p = trie[p][v];
        if (!p) {
            break;
        }
    }
    return rank;
}

int getVal(int x) {
    int p = 0, val = 0;
    for (int i = 25; i >= 0; --i) {
        if (cnt[trie[p][0]] >= x) {
            p = trie[p][0];
        } else {
            x -= cnt[trie[p][0]];
            p = trie[p][1];
            val |= 1 << i;
        }
    }
    return val;
}

int getPrev(int x) {
    return getVal(getRank(x));
}

int getNext(int x) {
    return getVal(getRank(x + 1) + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            Insert(x + offset);
        } else if (op == 2) {
            Delete(x + offset);
        } else if (op == 3) {
            cout << getRank(x + offset) + 1 << '\n';
        } else if (op == 4) {
            cout << getVal(x) - offset << '\n';
        } else if (op == 5) {
            cout << getPrev(x + offset) - offset << '\n';
        } else {
            cout << getNext(x + offset) - offset << '\n';
        }
    }
    return 0;
}

We can see that this 01trie implementation performs much better than the conventional implementations.

Closing Thoughts

This implementation rests on two ideas:

1. Use the binary lexicographic order of a 01Trie to maintain numeric ordering.
2. Use cnt to implement order statistics, then derive predecessors and successors from rank and kth.

With a manageable value domain, this offers a concise alternative with predictable complexity.