Segment/interval tree tutorial

I'm going to use a smaller range for simplicity. So the tree looks like this:

                     [1,8]
		 [1,4]                    [5,8]
   [1,2]       [3,4]        [5,6]      [7,8]
[1,1] [2,2] [3,3] [4,4] [5,5] [6,6] [7,7] [8,8]

Each of those nodes stores the information that you're trying to find for that range. If you want to query the range [1,8], you only need to inspect the root node. If you want to query the range [3,5], when at the root you need to split it in to two queries, based on the left and right children of the node. [3,4] and [5,5].

When it comes to updating, you can use the same fashion as above and a term called "lazy propagation". If you were to update range [1,8] you would effectively have to update every node in the tree. Lazy propagation means that you would only update node [1,8] and leave a flag that says that it's children need to be updated. Then when you have to query deeper than [1,8] you push the update down to the children, along with the flag. This way you only update when needed.

When you update [3,4] you have to let the result of the update filter back up to the root.

If you're looking for a simpler problem to start with, I used this one:
spoj.pl/problems/LITE/5

With lazy propagation, how to handle two consecutive update operations?? For example, if i first want to update the root [1,8], then i should update only [1,8] and flag [1,4] and [5,8] . Now if my immediate next operation is to update the interval [5,8], then what would be the necessary things to do?? Please help..

It all depends how you have implemented the tree. What is the value at [5,8]?

If you're solving LITE and the value at [5,8] is 0 then you simply need to turn off the update flag.

8 3
0 1 8
0 5 8
1 5 8

Yes, you are right. I am trying to solve LITE. In each node I'm storing the number of lights that are on within that interval. Actually I'm more bothered about the node[1,4]. When I update [1,8] then [1,4] and [5,8] are flagged. Next if I want to update node [5,8] then should I also update [1,4] (since [1,4] is flagged) and then propagate the result back to [1,8] (by adding the values of [1,4] and [5,8])??

In my implementation, if a flag for a node is on, the value in that node is accurate, but he value for all nodes below it is not. Therefore I would not be worried about [1,4] but if your implementation is different you will need to figure that out.

Or you could cache the value of the node before you update it and subtract the difference after you update it, then you wouldn't have to worry about it. This adds extra constant memory complexity though.

Thanks leppy. Got AC. But with lazy propagation, it is still O(mlogn). It is not asymptotically faster. Is it?? Please correct me, if I'm wrong.

In the worst case it is tons faster. Each query or update takes at worst log(number of nodes). Without lazy propagation each update takes (number of nodes) at the worst.

100000 100000
0 1 100000
0 1 100000
...
...
0 1 100000

Yes. I see. Thanks. Without your tutorial on lazy propagation, it won't have been possible for me to solve LITE.

thanks leppy. your explanation indeed made things clearer. understanding topcoder's tutorial will be easier now.

Just great tu

Which one sandra?

No need to reply to the spammers

can you tell me the lazy propogation in little bit detail ? let's say, if i have [1,8], then if i want to update [3,5], then which nodes will have their flags 1 ? i mean how will i approach this ? thanks. in your case, [1,8] it is very easy to see. please xplain.