Wrote a persistent segment tree because I needed to use a treap in a simulated contest, but I had never written one before...
I wrote it based on my memory of the courses I took back then, because I couldn't understand many blogs I read
Overview#
Whenever there is a modification operation, copy the node that needs to be modified and perform the modification on the copied node. This modification also includes modifications to the connection structure between points. Then, store the root node of each version in the root array.
Structure#
This segment tree needs to dynamically allocate nodes, so we need a struct
struct node {
int l, r; // corresponding interval
int ch[2]; // 0: left child, 1: right child
int v; // value
} c[MAXN];
Then we need an array to store the initial elements and the root array
int a[MAXN], root[MAXN];
We also need to keep track of the latest node and the latest version
int newp, newv;
Operations#
In all operations, pay attention to the fact that newp will change after recursive operations.
Building the Tree#
Similar to a regular segment tree
First, initialize the l and r of the root node
root[++newv] = ++newp;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
c[newp].l = 1;
c[newp].r = n;
void build (int p) {
if (c[p].l == c[p].r) {
c[p].v = a[c[p].l];
}
else {
++newp;
int son = newp; // save the current node. It cannot be used after newp changes
c[son].l = c[p].l;
c[son].r = (c[p].l + c[p].r) >> 1;
c[p].ch[0] = son;
build(son);
c[p].v += c[son].v;
++newp;
son = newp;
c[son].l = ((c[p].l + c[p].r) >> 1) + 1;
c[son].r = c[p].r;
c[p].ch[1] = son;
build(son);
c[p].v += c[son].v;
}
}
Querying#
Similar to a regular segment tree
Split into two functions very elegantly
int rq(int p, int l, int r) {
if (c[p].l >= l && c[p].r <= r) { // completely within the range
return c[p].v;
}
else if (c[p].r < l || c[p].l > r) { // completely outside the range
return 0;
}
else {
int s = 0;
s += rq(c[p].ch[0], l, r);
s += rq(c[p].ch[1], l, r);
return s;
}
}
int query (int v, int l, int r) {
return rq(root[v], l, r);
}
Modification#
The only difference from a regular segment tree
int ra (int p, int x, int k) { // return value: the newly created node after modification in the current version
if (c[p].l == c[p].r && c[p].l == x) {
c[++newp] = c[p];
c[newp].v += k;
return newp;
}
else {
if (c[p].r < x || c[p].l > x) return p; // if there is no modification, continue to use the original node
else {
int son = ++newp;
c[son] = c[p];
c[son].ch[0] = ra(c[p].ch[0], x, k); // update its own children
c[son].ch[1] = ra(c[p].ch[1], x, k);
c[son].v = c[c[son].ch[0]].v + c[c[son].ch[1]].v;
return son;
}
}
}
void add (int v, int x, int k) {
int p = root[v];
root[++newv] = ra(p, x, k); // root node of the new version
}
Others#
However, this cannot achieve interval modification.
But the template problem doesn't require it
If you want to perform interval modification, just use the lazytag as usual, and there is no need to create a new version when querying. It's very simple...
Also, every time I write such a long data structure, I always feel that it would look better if written with pointers.
Double Experience#
P3834 [Template] Persistent Segment Tree 1 (Treap)
P3919 [Template] Persistent Array (Persistent Segment Tree/Balanced Tree)
I got double experience because I used binary search to pass the treap problem