Range minimum query using Segment Trees

Segment tree is a tree data structure that stores segments. It can be used efficiently to query on a range to perform some aggregation such as query for range minimum, sum of range etc in O(log n) time. It can be built in O(n log n) time.

The segment tree is similar to a heap structure, an array can be used to represent it. The children of a node i is therefore 2*i and 2*i+1. Each node in a segment tree represents a segment, root node represents segment A[0..n-1] its left and right child represent segments A[0…n/2] and A[n/2+1..n] respectively.

From the tree structure, at level one we have one root node, at level two we have 2 nodes, level three we have 4 nodes and so on until level n where we have n nodes each representing an element in the initial array. Hence the size of the segment tree is:
1+2+4+....N/2+N < 2N

 

// RMQ by using segment tree
#include <bits/stdc++.h>

using namespace std;
const int MAX = 8; // max size of array

int n,Tree[3*MAX];  // segment tree total nodes will be around 2Max
/**
 * function to build a segment tree
 * Initially called as build(arr,1,0,arr.size()-1)
 * @param arr    intitial array, contents of which will be in the leaves of segment tree
 * @param vertex current vertex of segment tree (index starting from 1)
 * @param low    left most array arr's index for a pirtucular instance in recursion
 * @param high   right most array arr's index for a pirticular instance in recursion
 */
void build(int arr[],int vertex,int low,int high)
{
  if(low==high){
    Tree[vertex]=arr[low];
    cout<<"Tree["<<vertex<<"]:"<<arr[low]<<endl;
  }
  else
  {
    int mid = (low+high)/2;
    build(arr,2*vertex,low,mid);               // Segment tree's left child's index: 2*v (like heap)
    build(arr,2*vertex+1,mid+1,high);          // Segment tree's right child's index: 2*v+1
    Tree[vertex] = min(Tree[2*vertex],Tree[2*vertex+1]);
    cout<<"Tree["<<vertex<<"]:"<<arr[low]<<endl;
  }
}

/**
 * queries for min within [range_left,range_right]
 * low and high are array indexes
 * @param  vertex      current vertex of segment tree
 * @param  low         left arr arrays index for an instance in recursion
 * @param  high        right arr arrays index for an instance in recursion
 * @param  range_left  left index of the range for RMQ
 * @param  range_right right index of the range for RMQ
 * @return             returns range minimum query
 */
int query(int vertex,int low,int high,int range_left,int range_right)
{
  if(range_left>high || range_right<low)
    return INT_MAX;
  if(low >= range_left && high <= range_right)
    return Tree[vertex];
  else
  {
    int mid = (low+high)/2;
    return min(query(vertex*2,low,mid,range_left,min(mid,range_right)),
              query(vertex*2+1,mid+1,high,max(mid+1,range_left),range_right));
  }
}

/**
 * updates the segment tree for a change in input arr at index with a value
 * @param vertex current vertex of segment tree
 * @param low    left arr array's index for an instance in recursion
 * @param high   right arr array's index for an instance in recursion
 * @param index  index at which arr is changed
 * @param value  new value specified at given index
 */
void update(int vertex,int low,int high,int index,int value)
{
  if(low==high){
    Tree[vertex]=value;
    return;
  }
  int mid = (low+high)/2;

  if(index<=mid)
    update(2*vertex,low,mid,index,value);
  else
    update(2*vertex+1,mid+1,high,index,value);
  Tree[vertex]=min(Tree[2*vertex],Tree[2*vertex+1]); 
}
int main()
{
  int arr[]={1,3,5,7,9,11};
  build(arr,1,0,5);

  cout<<"MIN in range[2,5]"<<query(1,0,5,2,5)<<endl;
  update(1,0,5,2,0);
  cout<<"MIN in range[2,5]"<<query(1,0,5,2,5)<<endl;
}

 

Advertisements

Switching to Sublime Text and Essential Packages needed to get started

I have used vim for about six months now, and I fell in love with it. Learning vim boosts your productivity to an entire new level. But it has a pretty hard learning curve. It took some time for me to completely get used to vim. But my biggest problem with vim was installing packages and getting them working (Just getting auto-complete to work with vim took me a lot of time, then again, I was just a newbie). Hence I switched to Sublime Text and I fell in love with it.

I could still use vim’s features by turning on Sublime Text’s Vintage Mode. It looks so good (although looks don’t really matter), works so well! I suggest anyone having trouble with vim or working on any other editor to try it.

So the first and the foremost thing after installing Sublime Text (2/3) is to install Package Control, a package manager https://sublime.wbond.net/. Once done you can install packages in literally a few seconds, without any hassle!.

So here are the packages that are very handy:

  • Emmet: (must have for any front-end developer): Previously called Zen-Coding. Your HTML and CSS can be coded blazingly fast with just abbreviations which expands to valid HTML tags which is just a tab away!
  • Git: integrates git with Sublime Text, now all git commands can be run through Sublime Text.
  • Soda: The most aesthetic SublimeText theme I have come across.
  • BracketHighlighter: Bracket and tag highlighter.
  • SublimeLinter: For code linting.
  • Origami: Split window in any way you like.

There are so many more out there. Check them out.