Persistence Made Simple - Tutorial

Okay, i finished reading this after some more brushing up of the topic, and it literally is one of the best tutorial i ever read. It explains the concept very simply and easily. Also, i like your writing style, its not that monotonous one we find in textbooks, so it was a refreshing read.

For suggestion, We dealt with update function and build function here. Is it possible to take up some sample/standard problem and explain the query function as well? I am in doubt that, since we are creating new node instead of updating the old ones, what change in query function is necessary?

2 Likes

This problem is based on Persistent Trie

Dexter’s Random Generator

4 Likes

Awesome article upon this topic. Along with it, by seeing other answers, I wish to add.

I don’t know if many of us are aware of less advertised tag feature on CodeChef present at CodeChef: Practical coding for everyone.

Ex: These problems are related to persistence directly. Persistence Coding Problems - CodeChef

alt text

alt text

alt text

alt text

alt text

PS: Wrote especially as separate answer, to tell about tags, those weren’t knowing about it already. :smiley:

3 Likes

Nice tutorial!!! Can you provide the pseudo code in case we are doing a range update using lazy popagation??

4 Likes

Nice Tutorial man!!!

2 Likes

This is an answer to @blake_786’s question regarding updates with lazy propagation, since my answer would not fit into a comment.

Persistent Lazy Propagation

Lazy propagation is the act of updating by need. To do lazy propagation with a persistent tree, like for regular segment tree, we flag nodes whenever they need to update and subsequently pass them down to the children after visiting. But the difference is, since we are doing things persistently, we create new nodes during update.

The thing is, propagation varies from problem to problem. Range set-value update is different from range increase, range flip, etc. But the template is similar. Let’s make two arrays, hasflag[] and flag[] to mark if a node has a lazy flag or not. Then the code of persistent propagation will look like the following:

bool hasflag[]; // if node has a flag (sometimes, you can omit this)
int flag[];     // the actual value of the flag

// returns a new node with a lazy flag
int newlazykid(int node, int delta, int L, int R);

void propagate(int p, int L, int R) {
    if (hasflag[p]) {
        if (L != R) { // spread the laziness
            l[p] = newlazykid(l[p], flag[p], L, M);
            r[p] = newlazykid(r[p], flag[p], M + 1, R);
        }
        // reset flag
        hasflag[p] = false;
    }
}

The propagate() method spreads the laziness from parent to children. In doing so, we update the values of the children depending on our flag. But if you notice, we want persistence so the way to update this is to create “new lazy kids” during propagation. (Note, we don’t need to create a “new non-lazy parent” node after propagation, since it’s the same parent that was just too lazy to update).

Lazy Children

To propagate properly, we need a way to create lazy child nodes. That’s what the newlazykid() method is for. I left it blank since the propagation style largely depends on the problem. But by default, the lazy kid should make a new cloned node, update it, then setup its flags. Here’s an example template code:

int newlazykid(int node, int delta, int L, int R) {
    int p = ++NODES;
    l[p] = l[node];
    r[p] = r[node];
    flag[p] = flag[node]; // need this since lazy kid might be lazy before
    hasflag[p] = true;
    
    /* range increase */
    flag[p] += delta;
    st[p] = st[node] + (R - L + 1) * delta;
    /* edit depending on the problem */
    
    return p;
}

After setting up flags, the child needs to know what needs to change based on the flag. It depends on the problem. For example, for range increase the kid can have value st[node] + (R - L + 1)*delta. If it’s range set-value we simply make the kid have value delta, if it’s range minify the value is min(st[p], delta) and so on.

Lazy Range Update/Query

Now that we have propagation, how does the final range update code look like? It’s amazingly succint if you ask me :slight_smile:

// range update on [a:b] with value x, on the tree rooted at p

int update(int a, int b, int x, int p, int L=0, int R=n-1) {
    if (b < L || R < a)   return p;
    if (a <= L && R <= b) return newlazykid(p, x, L, R); 
    propagate(p, L, R); // always do this before going down
    return newparent(update(a, b, l[p], x, L, M),
                     update(a, b, r[p], x, M + 1, R));
}

Now, every time we query down we should also propagate. We’ll achieve very similar code after.

// range query on [a:b], on the tree rooted at p

int query(int a, int b, int p, int L=0, int R=n-1) {
    if (b < L || R < a)   return 0;
    if (a <= L && R <= b) return st[p];
    propagate(p, L, R); // always do this before going down
    return query(a, b, l[p], x, L, M) + query(a, b, r[p], x, M + 1, R);
}

Hope that was helpful. I’d like to have your thoughts on this.

20 Likes

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 SPOJ.com - Problem 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

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

So well explained.

nice tutorial

1 Like

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

best tutorial for leaning all about persistent segment tree.

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

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

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?

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