Persistence Made Simple - Tutorial

Yes, basic knowledge is enough. If you have done RSQ or RMQ, even without lazy propagation, I believe you can understand how persistence works

4 Likes

Amazing article!

1 Like

Good question. To revert, you pass the root of an old version. Let’s say range set update, sample usage below:

int arr[] = {7, 1, 5, 2, 3}; n=5;
int tree0 = build(arr);
int tree1 = update(1, -4, tree0);  // {7, -4, 5, 2, 3}
int tree2 = update(2, -10, tree1); // {7, -4, -10, 2, 3};
int tree3 = update(4, -25, tree2); // {7, -4, -10, 2, -25};

// revert range [0..2] back to initial [tree0]
int tree4 = rangecopy(0, 2, tree3, tree0); // {7, 1, 5, 2, -25}

During recursion, the nodes of tree4 inside the range [0:2] will be the nodes from tree0. Hope that answers it ^

3 Likes

Linking some starting problems will make the amazing tutorial more complete, i guess. examples : MKTHNUM, SORTING etc.

5 Likes

Yes, that answers my question. Thanks a lot.

1 Like

This is great! Will add these problems to the list

It’s the same as segment tree. We’re not really creating new nodes during query (except when lazy), so it’s the same code. Except that instead of passing 2p and 2p + 1, we pass l[p] and r[p] during recursion:

// Example RSQ, call sum_query(a, b, root)

int sum_query(int a, int b, int p, int L=0, int R=n-1) {
    if (b < L || R < a) return 0; // outside range
    if (a <= L && R <= b) return st[p]; // inside range
    return sum_query(a, b, l[p], L, M)
         + sum_query(a, b, r[p], M + 1, R);
}
2 Likes

Thanks!! I will re-attempt the questions with this in mind (got stuck at thinking part) ^^

Very nice ^^

Another problem

Thanks! See my other answer for lazy propagation above link

Let’s say I want to compare if array [1, 2, 2, 3, 4] is similar to [1, 2, 3, 3, 4]. My trees represent hashing of frequency tables {1:1, 2:2, 3:1, 4:1} and {1:1, 2:1, 3:2, 4:1}

 Tree 1             Tree 2
  [1, 2, 1, 1]        [1, 1, 2, 1]
    /      \            /      \
 [1, 2]  [1, 1]      [1, 1]  [2, 1]
  /  \    /  \        /  \    /  \
...                  ...

Look at second layer, there’s a special case where both left and right have mismatch, but the result is still “similar”. This can be solved by comparing rightmost and leftmost in both trees.

You’ll need to do LCA with jumping pointers. You have tree[a] contain all nodes from root to a (you can use range sum). Then to find out if c is in the path from a to b, you check if query(c, tree[a]) + query(c, tree[b]) - query(c, tree[parent(LCA(a, b))]) == 1 with principle of inclusion-exclusion :slight_smile:

Thanks mate, It is clear now. I’m gonna write a small post on persistent hash tree.

1 Like

Great ! thanks :slight_smile:

So when we are building PST(initially) we always build a copy of original SegT ? (As we are doing in build() function by calling newleaf() and newparent())

By convention yes, if you have an initial array. But if tree is empty at the start, you can make also do without build by assigning tree as null (0) at the start, and do point updates one by one (e.g. path-to-root problems)

and st[] here stores the sum of elements in pre-order fashion, not conventional parent to child [2*i,2*i+1] way, does it make things easy ?

KQUERY can’t be solved using persistent segment tree? I am getting TLE.

2 Likes

hey i have done DQUERY using MO’s algorithm,but i am unable to solve that using persistent segment tree.can you please share your code?