data mapping and lazy propagation in segment tree

Question

Looks like there is only one good article about lazy propagation in Segment Tree on entire internet and it is: http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296

I understood the concept of updating only query node and marking its child. But my question is what if I query child node first and parent node later.

In this tree (along with location in array of heap )

           0->[0 9]
      1->[0 4]    2->[5 9]
   3->[0 2] 4->[3 4]  5->[5 7] 6->[8 9]
 .....................................

First query, if I update [0 4], its data will be changed and its child will be flagged. Second query, is read state of segment [0 9].

Here I face the issue. My segment tree implementation is such that value of each node is sum of its left and right child. So when I update node's value I've to update it's all parents. To fix logical issue, now I'm updating all parent of node (till it reaches root of tree). But this is taking performance toll and my whole purpose of using segment tree for fast batch update is getting killed.

Can anyone please explain, where I'm going wrong in using segment tree?

Crowberry

When I implemented a segment tree, I had to do the same thing. You set the [0->4] node, mark each child, and then update the parent nodes all the way to the root. – Gigue

so your update was O(logN) ? also, in segment tree, if my range is 2 to 7, i'll update 3 segments. rt? [2 2], [3 4] [5 7] – Crowberry

O(2*logn) update. Yea, that's a worst case sort of update. I'd be curious if anyone knows a better approach. – Gigue

Just Fyi, Attackers might be trying to steal your information from www.spoj.pl . ;( – Micrococcus

Answer 1

I will contrast lazy update operation to a normal update operation and how this changes query operation.

In a normal single update operation you update the root of a tree and then recursively update only the needed part of the tree (thus giving you a O(log(n)) speed). If you will try to use the same logic for a range updates, you can see how it can deteriorate to O(n) (consider very broad ranges and see that you will mostly need to update both parts of the tree).

So in order to overcome this O(n) idea is to update the tree only when you really need it (query/update on the segment which was previously updated, thus making your updates lazy). So here is how it works:

• creation of a tree stays absolutely the same. The only minor difference is that you also create an array which holds information about potential updates.
• when you update the node of the tree, you also check whether it needs to be updated (from the previous update operation) and if it is - you update it, mark children to be updated in the future and unmark the node (being lazy)
• when you query the tree, you also check whether the node needs to be updated and if so update it, mark it's children and unmark it afterwards.

Here is an example of update and query (solving maximum range query). For a full code - check this article.

void update_tree(int node, int a, int b, int i, int j, int value) {
    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it
        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }
        lazy[node] = 0; // Reset it
    }

    if(a > b || a > j || b < i) // Current segment is not within range [i, j]
        return;

    if(a >= i && b <= j) { // Segment is fully within range
        tree[node] += value;
        if(a != b) { // Not leaf node
            lazy[node*2] += value;
            lazy[node*2+1] += value;
        }
        return;
    }

    update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
    tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}

and query:

int query_tree(int node, int a, int b, int i, int j) {
    if(a > b || a > j || b < i) return -inf; // Out of range

    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it
        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }
        lazy[node] = 0; // Reset it
    }

    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return tree[node];

    return max(query_tree(node*2, a, (a+b)/2, i, j), query_tree(1+node*2, 1+(a+b)/2, b, i, j));
}

Bricklaying

Thanks for the blog link. – Micrococcus

Answer 2

When you query a node in the segment tree, you need to make sure that all its ancestors, and the node itself, is properly updated. You do this while visiting the query node(s).

While visiting a query node, you traverse the path from the root to the query node, while taking care of all the pending updates. Since there are O(log N) ancestors you need to visit, for any given query node, the you do only O(log N) work.

Here is my code for a segment tree with lazy propagation.

// interval updates, interval queries (lazy propagation)  
const int SN = 256;  // must be a power of 2

struct SegmentTree {

    // T[x] is the (properly updated) sum of indices represented by node x
    // U[x] is pending increment for _each_ node in the subtree rooted at x 
    int T[2*SN], U[2*SN];

    SegmentTree() { clear(T,0), clear(U,0); }

    // increment every index in [ia,ib) by incr 
    // the current node is x which represents the interval [a,b)
    void update(int incr, int ia, int ib, int x = 1, int a = 0, int b = SN) { // [a,b)
        ia = max(ia,a), ib = min(ib,b); // intersect [ia,ib) with [a,b)
        if(ia >= ib) return;            // [ia,ib) is empty 
        if(ia == a && ib == b) {        // We push the increment to 'pending increments'
            U[x] += incr;               // And stop recursing
            return; 
        }
        T[x] += incr * (ib - ia);          // Update the current node
        update(incr,ia,ib,2*x,a,(a+b)/2);  // And push the increment to its children
        update(incr,ia,ib,2*x+1,(a+b)/2, b);
    }

    int query(int ia, int ib, int x = 1, int a = 0, int b = SN) {
        ia = max(ia,a), ib = min(ib,b); //  intersect [ia,ib) with [a,b)
        if(ia >= ib) return 0;          // [ia,ib) is empty 
        if(ia == a && ib == b) 
            return U[x]*(b - a) + T[x];

        T[x] += (b - a) * U[x];           // Carry out the pending increments
        U[2*x] += U[x], U[2*x+1] += U[x]; // Push to the childrens' 'pending increments'
        U[x] = 0;

        return query(ia,ib,2*x,a,(a+b)/2) + query(ia,ib,2*x+1,(a+b)/2,b);
    }
};

Deadhead

This is the most concise code I saw. It'll be tested with skyline problem. Thanks. – Micrococcus

After 81% passed, Time Limit Exceeded. ;( – Micrococcus

The coding problem: lintcode.com/problem/the-skyline-problem – Micrococcus

You can use a simpler solution for the skyline problem. Just sort the vertical lines (start and end) and maintain a heap of the "current" heights as you sweep from left to right. The maximum height gives the height of skyline. – Deadhead

Thanks for the quick reply. I did hash heap + sweep line solution in the first pass. I was looking for multiple solutions. ^_^ Since I just learned segment tree, I wanted to see can I use segment tree to solve more problems. ha-ha. – Micrococcus

And there is an interesting results after submit to leetcode: leetcode.com/problems/the-skyline-problem/discuss/61313/… . This simplified lazy propagation segment tree solution in Java version beat 95% submissions. But exactly same python version only beat 5% submissions. I'll try to see why the python version is so slow. – Micrococcus

U[x], What is U stands for ? – Micrococcus