Before in a segment tree, we could only perform range query and point update. What if we wanted to perform range update and range queries? Naively looping over every index and updating it would cause O(NlogN) time complexity per query, which is far too slow. Instead we need to use a lazy segment tree.
To perform updates in logN time, we need to store lazy flags in each node. Every time we update, we don’t actually traverse the entire range, rather we add lazy flags at each node denoting the fact that we are about to update at the range.
We will have a few additional operations in our lazy segment tree:
apply(v, x, len):
At a current node v that spans length len, we want to add x to the entire range that v covers. We will add len * x to the node as that is how much sum we would add if we were to update the entire segment. Then, we will apply a lazy flag to v meaning that v’s children haven’t been updated yet and the next time we visit v, we must push our lazy flag onto the children.
push(v, x, len):
If our current node v has a lazy flag, then we should push_down onto our children. We can do this by calling apply() for both our children and passing our current lazy flag.
de