CODEWITHSUNDEEP
algorithmdata-structuresclrsinterval-tree
mkmostafa
mkmostafa

Reputation: 3171

Lazy propagation for Segmented Tree

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}

enter image description here

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

Upvotes: 0

Views: 183

Answers (2)

mkmostafa
mkmostafa

Reputation: 3171

Ok, I've found a the correct way to update the segment tree with lazy propagation for sums in that link.

Lazy propagation for sums

Upvotes: 0

hosyvietanh
hosyvietanh

Reputation: 286

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

  1. Increase value v for all of elements in range [i, j]
  2. 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));
}

Upvotes: 1

Related Questions