Segmented Trees

From Algorithmist
Jump to: navigation, search

Segment Tree[edit]

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[edit]

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[edit]

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

Related Problems[edit]

1>[FREQUENT][1]

2>[GSS1][2]

3>[GSS3][3]

4>[KGSS][4]