Mr.ink's blog

By Mr.ink, 8 years ago, In English

I am learning segment tree with lazy propagation but i can't find good tutorial. Can anyone post a code that implements this two operation with segment tree and lazy propagation:

a-add a value to every element in a interval b-get the. sum of interval.

Thanks in advance.

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a detailed article : http://se7so.blogspot.com/2012/12/segment-trees-and-lazy-propagation.html

  • Operation #1: Increment the elements within range [i, j] with value val
  • Operation #2: Get max element within range [i, j]
»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Here's my solution for SPOJ PROBLEM WHICH ASKS FOR THE SAME THING

Link Of Solution

Should I post comments also in my code as it is a little hard to read other people's code ?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%A8%D8%A7%D8%B2%D9%87%E2%80%8C%D9%87%D8%A7 in this page the second code is an implemention of a segment tree which can change a segment numbers to a number and find the maximum number of a segment.

»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Is lazy propagation always applicable for a segment tree problem ? Suppose we have to find the lcm of a given range, and there are range update operation of adding a number to the range. Is Lazy propagation applicable here?