×

# Need help with range update in segment tree

 0 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 answered 13 Sep '15, 20:15 3★kuruma 17.7k●72●143●209 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)
 0 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: Indicate if the children of that node were to be updated in past, What value was to be updated in the children, Hope it helps :) answered 14 Sep '15, 17:53 1.1k●1●8 accept rate: 10%
 0 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]);  } answered 14 Sep '15, 18:26 4★kay_kay 1.2k●7●21 accept rate: 20%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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