Segment trees


Here I like to discuss cool data structures and algorithms that can computer programmers become much better in what they do :) and its fun to learn and discuss , so lets learn something called 'Segment trees'

Before we talk about what it does , lets discuss whats the need for such a data structure.

Suppose we have an array of N numbers a[1],a[2],....a[N] Now I have two operations that I can perform on this array
  • Retrieve the sum of any sub-array between index i..j
  • Modify the value of any element a[i]
So whats the complexity of each of these operations

  • Retrieve the sum of any sub-array between index i..j - Big-Oh(N) since the size of sub-array can vary from 1 to N
  • Modify the value of any element a[i] - Big-Oh(1) , ie. constant time

  • Now lets suppose N is very large then computing the size of each subarray is very costly so we need to think and find  a mechanism that helps to reduce the complexity of finding the sum of any sub-array of the given array.

    How??
    Thats where segment tree comes in....

    This is how a segment tree looks for an array int a[]={1,3,5,7,11} of 5 elements
    The leaf nodes are the array elements while the internal nodes are merging of index [i..j]

    As you can see a node of range [i..j] divides itself into its 
          left-child - [i..(i+j)/2]     and     right child [ (i+j)/2 + 1 ...j ] 
          

    Each node in the segment tree contains the sum of elements that constitute the segments the node represents.
    Eg.  sum[0-2] = 1+3+5=9 is shown by the left-child of the root that represents the segment [0-2]

    So what did we really gain from this data structure...

    Since this is a balanced binary tree- we are breaking the segment into equal halves at each node 

    The height of the tree is O(logN). Thus if we want to find the sum of elements of any segment [i..j] we can find that in O(logN) time!!!

    We have reduced the time complexity from O(N) to O(logN) !!!
    Thats cool but there is a downside too, now if i want to change the value of any element then the change in the value of element a[i] will change the sum of every segment that contains the element i,
    Thats is all sub-arrays that contain the element a[i]

    So we need to update the value of all such nodes in the segment tree whenever an element is modified.

    How to do this ... First calculate the change 'c' in element a[i](whether +ve or -ve) and then
     simply traverse the path from root to the leaf that shows a[i] and update every node intermediate node adding the value 'c' to the it.

    This costs us O(logN)

    Thus segment tree gives the following complexities for the 2 operations we wanted to do:
    • Retrieve the sum of any sub-array between index i..j  - O(logN)
    • Modify the value of any element a[i] - O(logN)
    The following code constructs a sample segment tree

    
    #include <iostream>
    #define f(i,n)  for(int i=0;i<n;++i)
    #define LL long long
    using namespace std;
     
    struct treenode
    
    {
     int begin;
     int end;
     LL sum;
    treenode *left,*right;
    };
     
    LL construct_segtree(treenode*& root , int begin,int end,int a[])
    {
     if(root==NULL){
      root=new treenode();
      root->begin=begin;
      root->end=end;
      root->left=root->right=NULL;
     }
     
        if(begin==end){root->sum=a[begin];return root->sum;}
        
        //else
        int mid=(begin+end)/2;
        
        root->sum=construct_segtree(root->left,begin,mid,a)+construct_segtree(root->right,mid+1,end,a);
     
    return root->sum;
    }
     
    LL findsum(treenode*& t , int i , int j)
    {
     if(t->begin==t->end)return t->sum;
     
     if(t->begin==i && t->end==j)return t->sum;
     
     //in between
     int mid=(t->begin+t->end)/2;
     
     if(i<=mid&&j<=mid)return findsum(t->left,i,j);
     if(i>mid)return findsum(t->right,i,j);
     if(i<=mid&&j>mid)return findsum(t->left,i,mid) + findsum(t->right,mid+1,j);
    }
     
    void addval(treenode*& t , int i , LL val)
    {
     //update every node on path
     t->sum+=val;
     //base case
     if(t->begin==t->end)return;
     //else
     int mid=(t->begin+t->end)/2;
     
     if(i<=mid)addval(t->left,i,val);
     else addval(t->right,i,val);
     
    }
     
    int main() {
     
            int a[N];
     f(i,N)cin>>a[i];
     treenode* root=NULL;
     construct_segtree(root,0,N-1,a);
     //segment tree constructed 
     return 0;
    } 
    
    Hope it helps :)

    Comments

    Popular posts from this blog

    Find size of ArrayList in minumum steps

    Edit that pdf....