Need help with range update in segment tree

general
1

Hi,
I have a few doubts regarding segment trees range updates.

  1. I know how to use a segment tree for range query and single element update. But how do I use it for range updates as well as range query? For example, if the question is to find sum of elements in a range and add ‘v’ to all elements in the range, how do I do it?

  2. In the problem FlipCoins , I saw some solutions. They use another variable flip along with the head count. What is the purpose of that? I mean, why don’t we simply visit all the nodes in given range and flip the number of heads (interval size - previous number of heads)? Why are they using flip to change number of heads? At what point the code without flip variable fails?

  3. I noticed similar thing in the problem multiple of 3 . There also coders have used an extra variable.

p.s. Please answer without using lazy propagations. I haven’t understood that properly yet. And I believe every problem that uses lazy propagation can also be solved without it (may get TLE but answer will be correct).

2

Hi,

Getting TLE is not solving a problem :slight_smile: I know its a bit of a dramatic example but imagine a TLE on an airport scheudler?.. :slight_smile:

You can do a range update without lazy propagation by repeatdely calling the normal update function, which is, ofc, bound to give you TLE.

The extra variables you are referring to, are possibly the variables that coders used to “get” lazy propagation in their codes.

The idea is that you only update exactly what you need on higher levels of the segment tree, instead of updating every single node individually that could end up having the same result for a given range if you updated only a specific “implicit” node higer in the tree…

I havent coded lazy propagation before but this can help you:

3

Try solving the ADDMUL problem, it will solve your doubts.

Lazy Propagation use the idea that you just update what needs to be instead of all nodes of the segment tree in the range. We keep generally another variable in each node “lazy”, which is used to indicate if the child nodes need to be updated when they are traversed in future. So lazy is used to:

  1. Indicate if the children of that node were to be updated in past,
  2. What value was to be updated in the children,

Hope it helps :slight_smile:

4

For Range Update using Segment Tree(without Lazy Propogation), you have to change just one line in the code given in the above link.

    void update_tree(int node, int a, int b, int i, int j, int value) {

if(a > b || a > j || b < i) 
	return;

if(a == b) { 
		tree[node] += value;
		return;
}

update_tree(node*2, a, (a+b)/2, i, j, value);
update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); 

tree[node] = tree[node*2] + tree[node*2+1]);

}

5

I have read this blog. But the codes didn’t use similar coding. So I am confused. Can you please take a look at this accepted code and tell me whether it is lazy propagation or not?

1 Like
6
7