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


July 8, 2011 - Posted by | C++ | , , ,


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

    Comment by aman | March 28, 2012 | Reply

  2. please write the code for lazy propagation

    Comment by anonymous | June 30, 2012 | Reply

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s