Segment Tree : The general concept behind Lazy Propagation

Revision en1, by Komyona_neko, 2016-04-21 18:06:01

I have started to solve some Segment Tree problems recently and I had some queries about the Lazy Propagation Technique. I understand the basic concept of Lazy Propagation and have solved some problems (all of them in the format : Add v to each element in the range [i,j] , Answer the sum , maximum/minimum element ,some info for elements in range [a,b]). I got the concept for the adding element Lazy Propagation . But I have some confusion about changing the elements to v for all elements in the range [i,j] problem . My question is , what is the general concept that I should have in mind while finding solution for these and more harder variations? I have seen lots of code online but they are mostly for the first version of the problem which I think I understand but I just don't know how to apply this concept to solve other variation of Lazy propagation problem. And I also need some tips on debugging Segment tree problems.

Tags segment tree, segment trees, lazy propagation, advanced data structure

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Komyona_neko 2016-04-21 18:07:38 23
en1 English Komyona_neko 2016-04-21 18:06:01 1008 Initial revision (published)