Segmented Trees

Segment Tree

A segment tree is a tree-like data structure that store the intervals or segments.It can be used for making update/query operations upon array intervals in logarithmical time.

Recursive Definition 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].

Construction

Construction of segment tree take O(nlogn) time . Segment tree is constructed recursively starting from root in the same way as heap-data structure.

Algorithm:-

Suppose segment tree is required for interval [i,j].then

Function(i,j,index)
Set index=1.
1:If i==j ,node[index]=data[i],else goto step 2.
2:Take mid=(i+j)/2.
Function(index*2, i , mid).
Function(index*2+1 , mid+1 , j).
node[index]=Using data of( node[index*2],node[index*2+1]).

Example: Given an array of size N(large) containing numbers(let integers),and you are given Q(large) queries in which you are required to calculate

the sum of Intervals [i,j].where 0<=i<=j<=N.

Solution:

Time Complexity of single query is O(logn)(max),thus total time Complexity is O(Qlogn).

First Create Data Structure:

struct node
{
LL sum;
};

Then Construct Segment Tree:

node a[2*Size+1];
void Construct(int index,int start,int end)
{
if( start==end)
{
a[index]=data[start];
}
else
{
int mid=(start+end)/2;
Construct(index*2,start,mid);
Construct(index*2+1,mid+1,end);
a[index].sum=a[index*2].sum+a[index*2+1].sum;
}
}

It will create a segment tree of length N,with each node containing the sum b/t their corresponding Interval,root node i.e a[1] will contain the sum of whole array.

Query

In Every Query ,you are requested to provide the result of some operation with in some given interval suppose [i,j]

This can be done easily in the same way as in the construction.

node query(int ind,int i,int j,int start,int end)
{
if(i<=start&&j>=end)//if [i, j]  lies in the interval of node
return a[ind];
int mid=(start+end)/2;//take the mid interval
if(j<=mid)
return query(ind*2,i,j,start,mid);//go to left part
else if(i>mid)
return query(ind*2+1,i,j,mid+1,end);//go to right part
else
{
node p1,p2,p3;
p1=query(ind*2,i,j,start,mid);//calculate from left interval
p2=query(ind*2+1,i,j,mid+1,end);//calculate from right interval
p3.sum=p1.sum,p2.sum;
return p3;
}
}

1>[FREQUENT][1]

2>[GSS1][2]

3>[GSS3][3]

4>[KGSS][4]