## 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