# COME ON CODE ON

A blog about programming and more programming.

## Segment Trees

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]

See the picture below to understand more :

Segment Tree

We can use segment trees to solve Range Minimum/Maximum Query Problems (RMQ). The time complexity is T(N, log N) where O(N) is the time required to build the tree and each query takes O(log N) time. Here’s a C++ template implementation :

```#include<iostream>
using namespace std;
#include<math.h>

template<class T>
class SegmentTree
{
int *A,size;
public:
SegmentTree(int N)
{
int x = (int)(ceil(log2(N)))+1;
size = 2*(int)pow(2,x);
A = new int[size];
memset(A,-1,sizeof(A));
}
void initialize(int node, int start,
int end, T *array)
{

if (start==end)
A[node] = start;
else
{
int mid = (start+end)/2;
initialize(2*node,start,mid,array);
initialize(2*node+1,mid+1,end,array);
if (array[A[2*node]]<=
array[A[2*node+1]])
A[node] = A[2 * node];
else
A[node] = A[2 * node + 1];
}
}
int query(int node, int start,
int end, int i, int j, T *array)
{
int id1,id2;
if (i>end || j<start)
return -1;

if (start>=i && end<=j)
return A[node];

int mid = (start+end)/2;
id1 = query(2*node,start,mid,i,j,array);
id2 = query(2*node+1,mid+1,end,i,j,array);

if (id1==-1)
return id2;
if (id2==-1)
return id1;

if (array[id1]<=array[id2])
return id1;
else
return id2;
}
};

int main()
{
int i,j,N;
int A[1000];
scanf("%d",&N);
for (i=0;i<N;i++)
scanf("%d",&A[i]);

SegmentTree<int> s(N);
s.initialize(1,0,N-1,A);
while (scanf("%d%d",&i,&j)!=EOF)
printf("%d\n",A[s.query(1,0,N-1,i-1,j-1,A)]);
}```

Resources:

NJOY!
-fR0D

Written by fR0DDY

September 15, 2009 at 8:21 PM

Posted in Programming

Tagged with , , , , , , , ,

### 19 Responses

1. Hey, nice tut. If u add a tutorial for updating the values in segment tree, it will be great!

Boris

September 18, 2010 at 12:34 PM

2. when i five n= 800 in input then this code crashes.

Anuj

October 13, 2010 at 8:53 AM

berin

November 12, 2010 at 7:22 PM

4. could u plzzz add a good tutorial on binary indexed tree as they r easy to code????

aayush kumar

June 9, 2011 at 4:49 PM

• fR0DDY

June 9, 2011 at 8:30 PM

• Hi I Don’t Understand Whats the application of segment tree ? i mean if we can search the element in given range of sorted array in O(logn) then why we need such complex DS or m i missing sum-thing so do u mean we can find the elements in unsorted array in O(logn) is it so .?? as Heap can unsorted array as 5 4 3 1 2 isn’t it .?? also please explain the in detail the initialize & query part & also write update part as you have mentioned..i am really interest in algorithms & so i wants to know what we can do with segment tree once you will reply my question i will really look & analyze it…i mean really really interested & appreciate ur attempt.

i mean when i m giving input for i & j 0 ,5 or i=0 & j=1 to 9 for N=10 array then i am getting output of query is 0 m not getting what exactly query function is doing ?? whats the purpose of it does it s giving element in range or its searching particular element & returning that element.

Algoseekar

June 12, 2011 at 10:08 PM

• It can be used to find maximum/minimum element in a range of an unsorted array. Also between the queries also, you can update any element.

fR0DDY

June 15, 2011 at 10:27 PM

5. Bugs in the code above.
-> log is logarithm to the base 10, whereas log to the base 2 should be used.
-> only the position should be returned in line numbers 50,52,55,57.

To verify the bug run the code with the following input
N = 8
array = { 1, 2, 0, -1, 5, 5, 5, 5 }
first i,j -> 1 2 ( gives correct output of 0 )
second i,j -> 3 4 (gives incorrect output of 0)

mozzak

October 1, 2011 at 12:43 PM

• This is the output for this case- remember output is minimum element 🙂

8
1 2 0 -1 5 5 5 5
1 2
1
3 4
-1

shashank jain

August 2, 2012 at 7:25 PM

6. It would be better if in the tree initialization N = 2^X, you would get faster solution. Your current solution would get TL on some test cases… I don’t remeber testcases, but I promise you that N should be equal 2^x 🙂

vilvler

February 27, 2012 at 3:02 PM

• Why would it be faster if you are adding more nodes to the tree?

Andrés Mejía

February 28, 2012 at 5:38 AM

7. Nice tutorial, I also wanted to know about updation of segment trees. How is it achieved? Can you explain a little more?

aman

June 18, 2012 at 8:54 AM

8. hey how to implement if i need all intervals with 0<=i<j<n
like for eg in the above tree i need to fint the max from the interval [1,8]

aichemzee

December 9, 2012 at 2:55 AM

9. I beleive the time complexity of construction the segment tree is \$O(n\log n)\$.

Macropodus

February 23, 2013 at 9:51 PM

10. There’s a small bug, not so important yet proves pain in neck if tested under certain input ranges. For very large range say 1 to 100000. The Query function goes so deep in recursion that it exceeds the recursion depth & hence will result as “Segmentation Fault”. I’ve tried it locally on my machine and on online competition too to verify.

Ravi Ojha

May 12, 2013 at 1:59 PM

11. […] wcipeg.com/wiki/Segment_tree comeoncodeon.wordpress.com/2009/09/15/segment-trees/ letuskode.blogspot.com/2013/01/segtrees.html […]

12. […] en.wikipedia.org/wiki/Segment_tree wcipeg.com/wiki/Segment_tree comeoncodeon.wordpress.com/2009/09/15/segment-trees/ letuskode.blogspot.com/2013/01/segtrees.html p–np.blogspot.com/2011/07/segment-tree.html […]