Often we have to work with segments or intervals of a list of items. This is where segment tree among many others come into place.

In this post we are going to learn about this beautiful data structure namely segment tree.


Note : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.


Segment Tree

In computer science, a segment tree, also known as a statistic tree, is a tree based data structure used to store information about intervals or segments (hence the name). The segment tree was invented by Jon Bentley in 1977 in his paper "Solutions to Klee’s rectangle problems".

Each node of the segment tree stores a function of some interval of the elements of the array. Segment tree allows to effectively answer range queries and still being flexible to allow for changes in the underlying array.

Structure

The Segment tree holds the following properties :

  • Segment tree is a binary tree.
  • Leaves of the segment tree correspond to the elements of the array of items from which the tree is built.
  • Internal nodes of the tree represent intervals of elements of the array of items formed by taking the union of the intervals represented by its left and right child.
  • For an array of size n, the size of the segment tree is
Size of Segment Tree

Internally, the segment tree is stored in the form of an array where for a node at index i its left child is at the index 2*i+1 and its right child is at the index 2*i+2.

Segment Tree Example
Segment Tree Example

Build

The buildSegmentTree is a recursive procedure that builds the segment tree from the underlying array. The procedure uses a divide and conquer approach to build the segment tree.

It takes in four parameters :

  1. array : The underlying array from which the segment tree is built.
  2. left : The index of the left side of the segment.
  3. right : The index of the right side of the segment.
  4. index : The index of the element in the segment tree which stores information about the segment elements array[left]...array[right].

Like every other divide and conquer procedure, this procedure consists of three steps :

  1. Divide : In this step, the procedure breaks the segment into two sub-segments.
  2. Conquer : In this step, the procedure solves the sub-segments recursively with the base case arising when the segment consists of only one element whereby segmentTree[index]=array[left]
  3. Combine : In this step, the procedure combines the solutions to the two sub-segments (left and right child) using the function func to arrive at the solution for the segment.

Pseudo Code :

buildSegmentTree(array,left,right,index)
    if left<right
        return
    if left==right
        segmentTree[index]=array[left]
        return
    mid=(left+right)
    buildSegmentTree(array,left,mid,2*index+1)
    buildSegmentTree(array,mid+1,right,2*index+2)
    segmentTree[index]=func(segmentTree[2*index+1],segmentTree[2*index+2])

Time Complexity : O(N)

Query

The querySegmentTree returns the value func(start...end) for a given segment start...end.

The querySegmentTree procedure takes in six arguments :

  1. left : Left index of the segment in segmentTree[index].
  2. right : Right index of the segment in segmentTree[index].
  3. index : Index of the current segment tree element.
  4. start : Left index of the desired segment.
  5. end : Right index of the desired segment.
  6. val : Value of func(start...end) that is to be returned at last.

For every segment left...right there may be three situations that can arise :

  1. Segment start...end is completely or partially inside the segment : In this situation, we simply recursively call querySegmentTree for both the left and right child.
  2. Segment start...end is completely outside the segment : In this situation, we have no chance of reaching any element in the segmentTree which is part of the segment start...end, hence we simply return
  3. Segment is completely inside the segment start...end : In this situation, we have reached at a part of the segment start...end and hence we simply append the value in the segmentTree[index] to val.

Pseudo Code :

querySegmentTree(left,right,index,start,end,val)
    if left>start&&right<end
        return
    if left<=start&&right>=end
        val=func(val,segmentTree[index])
        return
    mid=(left+right)/2
    querySegmentTree(left,mid,2*index+1,start,end,val)
    querySegmentTree(mid+1,right,2*index+2,start,end,val)

Time Complexity : O(log(N))

Update

The updateSegmentTree is a simple procedure that updates a given position in the underlying array and rebuilds the whole segment tree with the updated array.

The updateSegmentTree procedure takes in six arguments :

  1. array : The underlying array from which the segment tree was built
  2. left : Left index of the segment in segmentTree[index].
  3. right : Right index of the segment in segmentTree[index].
  4. index : Index of the current segment tree element.
  5. pos : Index of the position to be changed
  6. val : New value to be assigned to array[index]

Pseudo Code :

updateSegmentTree(array,left,right,index,pos,val)
    if left==right
        array[pos]=val
        segmentTree[index]=val
        return
    mid=(left+right)/2
    if pos<=mid
        updateSegmentTree(array,left,mid,2*index+1,pos,val)
    else
        updateSegmentTree(array,mid+1,right,2*index+2,pos,val)
    segmentTree[index]=func(segmentTree[2*index+1],segmentTree[2*index+2])

Time Complexity : O(log(N))


Segment trees are a very good data structure in situations where segment or range queries are a very common affair. However there is a very similar data structure to Segment Tree known as Fenwick Tree (FT) or Binary Indexed Tree (BIT) but we will look at this data structure at a later point in time.