Lazy propagation for Segmented Tree

Question

There is something unclear to me in the lazy propagation algorithm for segmented trees. According to the code below, upon completely overlap of the query interval, the update value is just added to the parent node and the children are marked for lazy updates. But as you can see in the image attached, if an update is done +4 for range 0,1 the result is totally different in both trees! (left image: no lazy propagation).

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}

So the question is, what if a query asking for the sum from 0,1 was invoked after the +4 update?

hosyvietanh hosyvietanh · Accepted Answer · 2015-08-14T17:46:46

First, it seems that the purpose of your implementation is to serve 2 operations.

Increase value v for all of elements in range [i, j]
Query the max value of a range [i, j] (I see it from the last line)

You're asking about query a sum of a range, which is probably not possible with the way you update your tree[node].

Second, you should use lazy propagation from both update function and query function.

I will assume you're trying to query max value of range [i, j]. You should probable get some code like this:

int query_max(int node, int a, int b, int i, int j) {
    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 -INFINITY;
    }
    if(a >= i && b <= j) { // Segment is fully within range
        return tree[node];
    }
    return max(query_max(node*2, a, (a+b)/2, i, j), query_max(node*2+1, a, (a+b)/2+1, i, j));
}

Lazy propagation for Segmented Tree

2 Answers