Persistence Made Simple - Tutorial

tutorial
, ,
13

hey @hikarico I’m trying to understand your approach(CodeChef: Practical coding for everyone) in June17 CLONEME question. You have used persistent hash tree. but I’m not getting your approach from line 133. If the left or right any of them are not equal then we are searching for leftmost or rightmost, but it could be in between also…? did I misunderstand something here?

I dont have enough karma points to reply to your comment on original post.

1 Like
14

So well explained.

15

nice tutorial

1 Like
16

Has anyone solved [DQUERY][1] or [KQUERY][2] using persistent segment tree?

I have done these using segment tree and offline approach.

Edit: done both using persistent segment tree also.
[1]: SPOJ.com - Problem DQUERY
[2]: SPOJ.com - Problem KQUERY

17

best tutorial for leaning all about persistent segment tree.

18

One of the best tutorial I ever saw.
Great work.

19

Could somebody give me the implimentation of this problem with this code of persistent seg tree please.I don’t know why it gives me wrong answer. This problem

The code

20

Just a basic knowledge of segment trees is enough? I have just started wth this thing (solved Q on minimum in range [l,r] and other basic ones). Will that be enough to understand it? Or do i need to see/practice more before starting this?

21

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
22

Amazing article!

1 Like
23

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
24

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

5 Likes
25

Yes, that answers my question. Thanks a lot.

1 Like
26

This is great! Will add these problems to the list

27

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
28

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

29

Very nice ^^

30

Another problem

31

Thanks! See my other answer for lazy propagation above link

32

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.