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

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

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

**array**: The underlying array from which the segment tree is built.**left**: The index of the left side of the segment.**right**: The index of the right side of the segment.**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 :

**Divide**: In this step, the procedure breaks the segment into two sub-segments.**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]***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 :

**left**: Left index of the segment in segmentTree[index].**right**: Right index of the segment in segmentTree[index].**index**: Index of the current segment tree element.**start**: Left index of the desired segment.**end**: Right index of the desired segment.**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 :

- 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. - 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 - Segment is completely inside the segment
*start...end*:*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 :

**array**: The underlying array from which the segment tree was built**left**: Left index of the segment in segmentTree[index].**right**: Right index of the segment in segmentTree[index].**index**: Index of the current segment tree element.**pos**: Index of the position to be changed**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.