Ronzii's Blog

Just your average geek's blog

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:

Basics of lazy propagation

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

Advertisements

July 8, 2011 Posted by | C++ | , , , | 2 Comments