data mapping and lazy propagation in segment tree

algorithm, data-mapping, data-structures, segment-tree

Solution

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));
}

Problem

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?

Original source