## Segment Tree Tutorial

Topcoder is a good source to get started on segment tree. But they tell very little about a little technique known as lazy propagation. Starting with the basics :-

A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time. We define the segment tree for the interval **[i, j]** in the following recursive manner:

- the first node will hold the information for the interval
**[i, j]** - if i<j the left and right son will hold the information for the intervals
**[i, (i+j)/2]**and**[(i+j)/2+1, j]**

Notice that the height of a segment tree for an interval with **N** elements is **[logN] + 1**. Here is how a segment tree for the interval **[0, 9]** would look like:

**General Approach’s Pseudocode**

The update function follows this logic in general

void update(int begin,int end,int i,int j,int n=1) { // If node is flagged, update it if(begin>=i && end<=j) { // If it is in the interval [i,j], then perform operation } else if(begin>=end) { // return if reaches leaf of heap } else { int mid = (begin+end)/2; // Call [i,mid] // Call [mid+1,j] // Update n's children // Update n } }

The query function is similar. Both have complexity of O(log(n)) and they have really helped me crack some pretty good SPOJ problems

can you explain more about it, it doesn’t seem enough to satisfy my hunger.

Comment by aman | March 28, 2012 |

please write the code for lazy propagation

Comment by anonymous | June 30, 2012 |