Introduction
Chinese Version:Luogu Link(IN QUEUE,ONLY INTERNATIONAL WEB)
Translate by Gemini 3-flash.
There isn't much to introduce. I’ve spent so much time learning Treaps with rotations, only to find that there are almost no resources online regarding the persistent version of it. This annoyed me enough to write this article.
Note: Variable names used in this article are defined as follows:
| Variable | Meaning |
|---|---|
| $$$l_i, r_i$$$ | Left and right child indices of node $$$i$$$ (0 if non-existent) |
| $$$val_i$$$ | The value (key) of node $$$i$$$ |
| $$$rnd_i$$$ | The random priority of node $$$i$$$ |
| $$$cnt_i$$$ | The count of occurrences of $$$val_i$$$ |
| $$$siz_i$$$ | The total number of nodes in the subtree rooted at $$$i$$$ |
| $$$sz$$$ | Total number of nodes created (node counter) |
Persistence
First, let's briefly discuss what "persistence" is.
As we all know, when working on a project, you often encounter situations like:
"This version has a 'few' bugs. Please modify it. I've prepared some suggestions—they're in this 256MB zip file."
"Hmm, there are still some issues. In my humble opinion, these (points to 114,514 places) need fixing. Get to it."
"Sigh, why is every version worse? Forget it, the first version was the best. Revert everything back to Version 1."
If you didn't save the code for Version 1, you'd be ready to blow a fuse.
Persistence is essentially a "Save" mechanism:
Save historical versions.
Modify or query based on a specific historical version.
However, saving a full copy of the entire structure every time would obviously lead to an "MLE" (Memory Limit Exceeded). Therefore, persistent data structures use Path Copying: we only save the parts that have been modified.
In a Segment Tree, this is as easy as drinking water: you create new nodes for the modified path and point them back to the unchanged parts of the existing structure.
But, as is also commonly known, the structure of a balanced tree changes constantly compared to a Segment Tree. Implementing persistence on a balanced tree is notoriously difficult. Consequently, most persistent balanced trees are implemented using the structurally stable "Non-Rotating Treap" (also known as FHQ-Treap).
But is it truly impossible to implement a persistent Treap with rotations? (Absolutely not.)
Feasibility
Consider the logic of a Rotating Treap after a modification.
Let’s examine a standard insert function for a Rotating Treap:
void insert(int &k, int x) {
if (!k) {
sz++; k = sz;
siz[k] = 1; cnt[k] = 1;
val[k] = x; rnd[k] = rand();
return;
}
siz[k]++;
if (val[k] == x) {
cnt[k]++;
} else if (val[k] < x) {
insert(r[k], x);
if (rnd[r[k]] < rnd[k]) lrotate(k); // Left Rotate
} else {
insert(l[k], x);
if (rnd[l[k]] < rnd[k]) rrotate(k); // Right Rotate
}
}
You will notice that after a node is inserted, all nodes on the path from its parent up to the root may undergo rotations.
The rotation operation involves turning a parent into a child of its own child and re-hooking subtrees. If we adopt the logic of identifying children rather than parents during traversal, only the nodes involved in the rotation and their immediate ancestors change their state.
Therefore, we can simply copy these nodes before changing their state. Using a method similar to a Persistent Segment Tree (Chairman Tree), we point the new nodes back into the original tree and store the new root generated by this operation.
The same logic applies to the delete operation, which also modifies the structure. For queries, since the tree structure doesn't change, no copying is needed.
For every operation, we expect to copy $$$O(\log n)$$$ nodes. The complexities are:
Time Complexity per operation: $$$O(\log n)$$$
Total Space Complexity: $$$O(q \log n)$$$
Implementation
First, we implement a helper function to clone nodes. We create a new index and copy all data from the source node.
int copy(int k) {
if (!k) return 0;
++sz;
l[sz] = l[k]; r[sz] = r[k];
val[sz] = val[k]; cnt[sz] = cnt[k];
siz[sz] = siz[k]; rnd[sz] = rnd[k];
return sz;
}
Next, let's modify the insert and delete functions. For any operation that changes a node's state, we must first copy the node and then perform the modification on the clone.
Insertion Logic:
If the node to be inserted never existed, create it.
If the value already exists, copy the node and increment its count.
If we are traversing down, copy the current node, recurse, and perform rotations on the copied node during the backtracking phase.
int insert(int k, int x) {
if (!k) {
++sz;
l[sz] = r[sz] = 0;
val[sz] = x;
cnt[sz] = siz[sz] = 1;
rnd[sz] = rand();
return sz;
}
int nk = copy(k); // Copy first
siz[nk]++;
if (val[nk] == x) {
cnt[nk]++; // Exists, just increment count
} else if (val[nk] < x) {
r[nk] = insert(r[nk], x); // Recurse down
if (rnd[r[nk]] < rnd[nk]) lrotate(nk); // Maintain via rotation
} else {
l[nk] = insert(l[nk], x);
if (rnd[l[nk]] < rnd[nk]) rrotate(nk);
}
return nk;
}
Deletion Logic:
The logic is identical—copy before any state or structural change.
int del(int k, int x) {
if (!k) return 0;
int nk = copy(k); // Copy first
if (val[nk] == x) {
if (cnt[nk] > 1) {
cnt[nk]--;
siz[nk]--;
return nk;
}
if (!l[nk] || !r[nk]) {
return l[nk] | r[nk]; // Return the non-empty child
}
if (rnd[l[nk]] < rnd[r[nk]]) {
l[nk] = copy(l[nk]); // Copy child before rotating
rrotate(nk);
r[nk] = del(r[nk], x);
} else {
r[nk] = copy(r[nk]);
lrotate(nk);
l[nk] = del(l[nk], x);
}
upd(nk); // Update size after deletion
return nk;
}
if (val[nk] < x) {
r[nk] = del(r[nk], x);
} else {
l[nk] = del(l[nk], x);
}
upd(nk);
return nk;
}
Validation
This implementation passes the Luogu P3835 (Template: Persistent Balanced Tree).
Performance Results:
Slowest Time: 406ms
Peak Memory: 234.81MB
(Full source code is provided in the original post for reference.)
Afterword
Long live the Rotating Treap!!!
The claim that "only FHQ-Treaps can be persistent" is simply incorrect.
Of course, I encourage everyone to continue exploring other "exotic" persistent structures (Persistent Splay, Persistent Scapegoat Tree, Persistent AVL, etc.).
