Segment Trees

Segment Trees

What are Segment Trees ?

• In Competitive Contests, generally problem setters are keen to check the ability of applying data structures in questions. Segment trees are a data structure which are mostly used in giving solutions of Range Queries

BIT TREE vs Segment Trees ?

• BIT Tree have generally quite specific applications only thus it is less modifiable according to problem, mainly it can be used for range sum, max-min queries etc.
  In this case , Segment trees are quite widely used in many problems as they are more modifiable easily too.
• On the other hand, BIT Tree are easy to code as compared to Segment trees.
• Thus, it would depend on the programmer and time to code and problem to use which one easilty and that too fastly.

Structure

• A segment tree is a binary tree such that the nodes on the bottom level of the tree correspond to the array elements, and the other nodes contain information needed for processing range queries.A segment tree is a binary tree such that the nodes on the bottom level of the tree correspond to the array elements, and the other nodes contain information needed for processing range queries.

Time Complexity

• For each query or update O(log n) and for building it O(n * log n) is required.

Implementation

• While implementig Segment trees, often recursive manner is used.We bulit the tree in both the half parts and then merge the parts as per our needs . (See implementation below )

Question

• Perform the following queries on a given array :
  • Update the value at a given index
  • Query the minimum value in a given range in the array

int ar[100005];
int tree[500005];

void build(int node,int start,int end)
{
    if(start==end)
    {
        tree[node]=ar[start];
        return;
    }
   else
   {
     int mid=(start+end)/2;
     build(2*node,start,mid);
     build(2*node+1,mid+1,end);

     tree[node]=min(tree[2*node],tree[2*node+1]);

   }
}
void update(int idx,int value,int start,int end,int node)
{
    int mid=(start+end)/2;

    if(start==end)
    {
        ar[start]=value;
        tree[node]=value;
    }
    else
    {
        if(idx>=start&&idx<=mid)
        {
              update(idx,value,start,mid,2*node);
        }
       else 
       {
             update(idx,value,mid+1,end,2*node+1);
       }
        
        tree[node]=min(tree[2*node],tree[2*node+1]);
    }
}

int query(int l,int r,int start,int end,int node)
{
    if(end<l||start>r)   //checking whether range is out of L and R
       {
            return 1000000;
       }
    else if(l<=start&&end<=r)   // if the range is completely under L and R
        {
            return tree[node];
        }
    else                // if there is partial overlap between range and L and R
       {
           int mid=(start+end)/2;
           int p1=query(l,r,start,mid,2*node);      // Checking for answer in left part
           int p2=query(l,r,mid+1,end,2*node+1);    // Checking for answer in right part
           return min(p1,p2);
       }
}
int main()
{   
    IOS;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>ar[i];
    build(1,0,n-1);

    int q;
    cin>>q;
    char c;
    for(int i=0;i<q;i++)
    {
        cin>>c;
        if(c=='q')
        {
            int l,r;
            cin>>l>>r;
            cout<<query(l,r,0,n-1,1)<<endl;
        }
        else
        { 
            int idx,value;
            cin>>idx>>value;
            update(idx,value,0,n-1,1);
        }
    } 
}