segment tree with lazy propagation in large range

Question

Can anyone please tell me how lazy propagation works in a segment tree if we want to update values in a range? Also, how would we do this problem using a segment tree and lazy propagation?

Suppose there are 15 boys in a row, standing facing east, and we say that after 3 moves the range from [3,6] will be facing north, and after 2 moves they will be facing west. How would we update the range if our row size is around 10⁶?

Clockwise direction [EAST-->SOUTH-->WEST-->NORTH-->EAST]

For example: Suppose there are n students initially standing facing east, and we say we have to move students 3 to 6 two moves in a clockwise direction. Thus, after the move, the students will be like "e e w w w w e e e e". Then, we want to find the max number of students in a range standing facing the same direction. In this example, if we were to find the answer in the range [1,6], then there are 2 students facing east and 4 facing west, so the answer is 4.

Answer 1

http://wcipeg.com/wiki/Segment_tree#Lazy_propagation

To your problem:

Suppose we have N people. Then create a segment tree for addition with N leafs with value 0 initially. If you want to turn people with indices from i to j clockwise, you update [i..j] range with +1, if counterclockwise -- with -1.

Let's encode North = 0, East = 1, South = 2 and West = 3. For example, if people initially stand as "n e e s" in your notation it becomes "0, 1, 1, 2" after encoding.

Let's just sum the values (considering range updates!) from leaves of the tree to its accordings in encoded array (n log n). Pretend we turned people [1..2] counterclockwise, and two times [4] clockwise. Then after addition the array is "-1, 0, 1, 4".

Now apply the modulo operation to every number of the array: "3, 0, 1, 0". After decoding you get the final arrangement: "w n e n". Finding the most people facing the same direction is trivial now.