## Introduction↵
Chinese Version:[Luogu Link(IN QUEUE,ONLY INTERNATIONAL WEB)](https://www.luogu.com.cn/article/fqhiyvak)↵
↵
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:↵
↵
1. Save historical versions.↵
↵
2. 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:↵
↵
```cpp↵
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.↵
↵
```cpp↵
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:↵
↵
1. If the node to be inserted never existed, create it.↵
↵
2. If the value already exists, copy the node and increment its count.↵
↵
3. If we are traversing down, copy the current node, recurse, and perform rotations on the copied node during the backtracking phase.↵
↵
```cpp↵
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.↵
↵
```cpp↵
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)](https://www.luogu.com.cn/problem/P3835).↵
↵
**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.).
Chinese Version:[Luogu Link(IN QUEUE,ONLY INTERNATIONAL WEB)](https://www.luogu.com
↵
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:↵
↵
1. Save historical versions.↵
↵
2. 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:↵
↵
```cpp↵
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.↵
↵
```cpp↵
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:↵
↵
1. If the node to be inserted never existed, create it.↵
↵
2. If the value already exists, copy the node and increment its count.↵
↵
3. If we are traversing down, copy the current node, recurse, and perform rotations on the copied node during the backtracking phase.↵
↵
```cpp↵
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.↵
↵
```cpp↵
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)](https://www.luogu.com.cn/problem/P3835).↵
↵
**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.).
