Persistence Made Simple - Tutorial

suraj Unacademy Subscription
, ,
21

Very nice ^^

22

Another problem

23

Thanks! See my other answer for lazy propagation above link

24

Awesome! I mean how can anyone spend lots of time writing these blogs just for the sake of others … great tutorial …

Well I was trying http://www.spoj.com/problems/GOT/ question on spoj mentioned above …

I am using same approach as explained above but not able to implement it … Can someone help me or if possible send me the link of solution to this problem so that it might help me … Thanks in advance!

1 Like
25

hey @hikarico I’m trying to understand your approach(https://www.codechef.com/viewsolution/14097242) 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
26

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.

27

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:

28

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

1 Like
29

Great ! thanks :slight_smile:

30

So well explained.

31

nice tutorial

1 Like
32

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())

33

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)

34

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 ?

35

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

2 Likes
36

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]: http://www.spoj.com/problems/DQUERY/
[2]: http://www.spoj.com/problems/KQUERY/

37

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?

38

SPOJ set the time limit really strict for KQUERY, they specifically wanted offline solution for that with a faster data structure (e.g. fenwick). That’s why they created KQUERYO as a separate online problem.

2 Likes
39

I assume you did DQUERY by sorting queries by right endpoint? Then you can do the same technique using persistent tree. Same technique, but during build you store the tree at index R as tree[R]. You can now solve queries online, just call tree[R].range_query(L, R)

For KQUERY, the TLE is strict there so only offline works (cuz SPOJ)… but there’s an online counterpart KQUERYO, you can solve that with persistent

40

best tutorial for leaning all about persistent segment tree.