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