Problem statement
You'll be given an array of N<=100000 integers. And some M<=100000 queries. The queries are of two types: one asks to print the sum of values of a range, the other asks you to add some value to all the numbers in a range.
It's a standard application of lazy propagation or late update, whatever people prefer to say. It's a technique to update a range of values efficiently.
The following things are done when using late update: (Every time I use node as an array index, I mean it to be the current node)
1. During an update, every time a segment is fully inside the query interval, stop it right there. Update that interval. And remember that some value was added to the interval, like lazy[node] += x;
2. Otherwise, explore the left child and right child. Suppose you are at some node. If the value of lazy[node] is non zero, then it's known that the current node was updated but it's child wasn't. Update both child, and add the lazy value of current node to it's child nodes. Set the lazy[node] = 0;
3. Normal parent from child update follows.
4. During the retrieval only step number 2 should be taken care of.
Here is the code.
Mistakes I made:
1. Mixing index with endpoints, got two WAs, didn't even find the bug the first time :|
You'll be given an array of N<=100000 integers. And some M<=100000 queries. The queries are of two types: one asks to print the sum of values of a range, the other asks you to add some value to all the numbers in a range.
It's a standard application of lazy propagation or late update, whatever people prefer to say. It's a technique to update a range of values efficiently.
The following things are done when using late update: (Every time I use node as an array index, I mean it to be the current node)
1. During an update, every time a segment is fully inside the query interval, stop it right there. Update that interval. And remember that some value was added to the interval, like lazy[node] += x;
2. Otherwise, explore the left child and right child. Suppose you are at some node. If the value of lazy[node] is non zero, then it's known that the current node was updated but it's child wasn't. Update both child, and add the lazy value of current node to it's child nodes. Set the lazy[node] = 0;
3. Normal parent from child update follows.
4. During the retrieval only step number 2 should be taken care of.
Here is the code.
Mistakes I made:
1. Mixing index with endpoints, got two WAs, didn't even find the bug the first time :|
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন