This  blog is about square root decomposition.
Here we divide the entire elements into k parts such that each part has root(n) elements. In this manner only the last part will have <=root(n) elements. Now each query can be said to be connecting three regions    the first part of the range that doesnot lie completely in a interval the next part that lies in a interval totally and the next that doesnot lie totally
 Suppose we have an array of 11 element
     then the groups are (1) 1-3 (2) 4-6 (3) 7-9 (4) 10-11
Thus there are three  groups of root(11) size and the last one contains 2 elements.
 Suppose we want to obtain the sum of elements from 2 to 10
this can be done as arr[2]+arr[3]+sumofgroup(2)+sumofgroup(3)+arr[10]
It can be shown that the maximum complexity is 3root(n) and this tool is quite important
Here is a question (RMQ) solved using square root decomposition

RMQSQ - Range Minimum Query

no tags 

You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the minimum number between the range [i, j] (inclusive).
Note: the query ranges are specified using 0-based indexing.

Input

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).

Output

For each query, output the answer to that query on its own line in the order the queries were made.

Example

Input:
3
1 4 1
2
1 1
1 2

Output:
4
1

The code runs here!!!!

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
long long int inp[100010];
long long int arr[100010];

int n;
#include<math.h>
void build(int k)
{
   // cout<<"in build "<<endl;
    for(int i=0;i<n;i++)
    {
   //  cout<<i/k<<" "<<i<<endl;
       arr[i/k]=min(inp[i],arr[i/k]);
    }
 }
 
long long int  query(int low, int high,int k)
 {
   long long  int minval=INT_MAX;
  int i=low;
  //cout<<low<<" "<<high<<endl;
       while(i%k!=0 && i<=high)
        {
         minval=min(minval,inp[i]);
      //   cout<<"int part 1 "<<i<<" "<<endl;
         i++;
  }
  while(i+k<=high)
  {
      minval=min(minval,arr[i/k]);
  //    cout<<"int part 2 "<<i<<" "<<endl;
      i+=k;
  }
  while(i<=high)
  {
   minval=min(minval,inp[i]);
  // cout<<"int part 3 "<<i<<" "<<endl;
   i+=1;
  }
  return minval;
  } 
int  main()
{
 
 cin>>n;
 for(int i=0;i<n;i++)
 {
     scanf("%lld",&inp[i]);
 }
    int k=sqrt(n);
    for(int i=0;i<k+10;i++)
    arr[i]=INT_MAX;
    build(k);
    int q;
    cin>>q;
    int l,r;
    while(q--)
    {
       //cin>>l>>r;
       scanf("%d",&l);
       scanf("%d",&r);
       long long int ans=query(l,r,k);
       printf("%lld\n",ans);
 }
 return 0;
}

Related links and stuffs!!!

http://www.infoarena.ro/blog/square-root-trick 

Blog by anudeep on MO algorithm