Segment Tree : The general concept behind Lazy Propagation

Правка en2, от Komyona_neko, 2016-04-21 18:07:38

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

Теги segment tree, segment trees, lazy propagation, advanced data structure

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Komyona_neko 2016-04-21 18:07:38 23
en1 Английский Komyona_neko 2016-04-21 18:06:01 1008 Initial revision (published)