You are not logged in. Please login at www.codechef.com to post your questions!

×

Need help with range update in segment tree

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).

asked 13 Sep '15, 10:34

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%


Hi,

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

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:

http://se7so.blogspot.pt/2012/12/segment-trees-and-lazy-propagation.html

link

answered 13 Sep '15, 20:15

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

1

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?

(13 Sep '15, 22:28) dragonemperor3★

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 :)

link

answered 14 Sep '15, 17:53

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

http://se7so.blogspot.pt/2012/12/segment-trees-and-lazy-propagation.html

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

}

link

answered 14 Sep '15, 18:26

kay_kay's gravatar image

4★kay_kay
1.2k721
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,755

question asked: 13 Sep '15, 10:34

question was seen: 1,077 times

last updated: 14 Sep '15, 18:26