Wrote a persistent segment tree because I used a splay tree in a simulated contest, but I've 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, be aware 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, can't 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 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 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#
But this cannot achieve interval modification.
But that template problem doesn't require it
To achieve interval modification, simply add a lazytag and there is no need to create new versions 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 (Splay Tree)
P3919 [Template] Persistent Array (Persistent Segment Tree/Balanced Tree)
I got double experience because I used binary search to pass the splay tree problem