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

Queries on the String  Problem code: QSET

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

You have a string of N decimal digits, denoted by numbers A₁,A₂, ..., A_N.

Now you are given M queries, each of whom is of following two types.

• Type 1: 1 X Y: Replace A_X by Y.
• Type 2: 2 C D: Print the number of sub-strings divisible by 3 of the string denoted by A_C,A_C+1 ...
  A_D.
  
  
  Formally, you have to print the number of pairs (i,j) such that the string A_i,A_i+1...A_j,
  (C ≤ i ≤ j ≤ D), when considered as a decimal number, is divisible by 3.

Input

• There is only one test case.
• First line of input contains two space separated integers N, M.
• Next line contains a string of N digits, denoting string A.
• For next M lines, each line contains a query.
• Each query is given by three space separated integers.
• The first integer denotes type of the query. For each query of type 1, next two integers denote X_i, Y_i.
  For each query of type 2, next two integers denote C_i, D_i.

Output

For each query of type 2, print the required answer in a single line.

Constraints

• 0 ≤ A_i ≤ 9
• 1 ≤ X_i ≤ N
• 0 ≤ Y_i ≤ 9
• 1 ≤ C_i ≤ D_i ≤ N

Subtasks

• Subtask #1 (10 points): 1 ≤ N, M ≤ 10³ and only type 2 queries.
• Subtask #2 (15 points): 1 ≤ N, M ≤ 10³
• Subtask #3 (20 points): 1 ≤ N, M ≤ 10⁵ and only type 2 queries
• Subtask #4 (55 points): 1 ≤ N, M ≤ 10⁵

Example

Input:
5 3
01245
2 1 3
1 4 5
2 3 5

Output:
3
1

Explanation

For first query, the sub-strings S[1,1]="0", S[1,3]="012" and S[2,3]="12" are divisible by 3.
After second query, the string A becomes "01255".
For third query, only sub-string S[3,5]="255" is divisible by 3.

A very firm understanding of this question is the key to solve it .

For each node we require 4 things.    the number of substrings divisible by 3 on the segment , the total sum of the segment and the prefix and the suffix array .

where prefix array stands for the number of elements starting with the prefix and whose sum%3 gives 0,1 ,2. It is the same for prefix array. Now while ,merging two nodes , we first need to create the prefix and suffix arrays for the node. the prefix of a node is created by the total sum of the left child in combination with the prefix of the right child. the manner is given as:

(1) First we copy prefix array of the left child to the parent node.  then we combine it with the prefix of  the right array. Based on these conditions we use the prefix values on the right node.

(2) Similarly the suffix array of the parent node is calculated. 

(3) the total substrings in the parent is the sum of left and right node

tree[node].count+=tree[2*node].suf[0]*tree[2*node+1].pre[0];

tree[node].count+=tree[2*node].suf[1]*tree[2*node+1].pre[2];

tree[node].count+=tree[2*node].suf[2]*tree[2*node+1].pre[1];

we do the updates and queries similarly

     ********** here goes the code  ***************

#include<iostream>

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

long long int arr[100010];

struct segment

{

 long long int count;

 long long int sum;

 long long int pre[4];

 long long int suf[4];

}tree[500000];

void build(int node, int st, int end)

{

if(st>end)

return ;

if(st==end)

{

 tree[node].suf[(arr[st])%3]=1;

 tree[node].suf[(arr[st]+1)%3]=0;

           tree[node].suf[(arr[st]+2)%3]=0;

  tree[node].pre[arr[st]%3]=1;

  tree[node].pre[(arr[st]%3+2)%3]=0;

  tree[node].pre[(arr[st]+1)%3]=0;  

        if(arr[st]%3==0)

        tree[node].count=1;

        else

        tree[node].count=0;

        tree[node].sum=(arr[st]%3);

        return ;

}

build(2*node,st,(st+end)/2);

build(2*node+1,(st+end)/2+1,end);

tree[node].count=tree[2*node].count+tree[2*node+1].count;

tree[node].sum=(tree[2*node].sum+tree[2*node+1].sum)%3;

tree[node].pre[0]=tree[2*node].pre[0];

tree[node].pre[1]=tree[2*node].pre[1];

tree[node].pre[2]=tree[2*node].pre[2];

tree[node].suf[0]=tree[2*node+1].suf[0];

tree[node].suf[1]=tree[2*node+1].suf[1];

tree[node].suf[2]=tree[2*node+1].suf[2];

    if(tree[2*node].sum%3==0)

    {

     tree[node].pre[0]+=tree[2*node+1].pre[0];

     tree[node].pre[1]+=tree[2*node+1].pre[1];

 tree[node].pre[2]+=tree[2*node+1].pre[2];

}

else if(tree[2*node].sum%3==1)

{

tree[node].pre[0]+=tree[2*node+1].pre[2];

     tree[node].pre[1]+=tree[2*node+1].pre[0];

 tree[node].pre[2]+=tree[2*node+1].pre[1];

 

}

else

{

tree[node].pre[0]+=tree[2*node+1].pre[1];

     tree[node].pre[1]+=tree[2*node+1].pre[2];

 tree[node].pre[2]+=tree[2*node+1].pre[0];

}

if(tree[2*node+1].sum==0)

{

tree[node].suf[0]+=tree[2*node].suf[0];

tree[node].suf[1]+=tree[2*node].suf[1];

tree[node].suf[2]+=tree[2*node].suf[2];

}

else if(tree[2*node+1].sum==1)

{

tree[node].suf[0]+=tree[2*node].suf[2];

tree[node].suf[1]+=tree[2*node].suf[0];

tree[node].suf[2]+=tree[2*node].suf[1];

 

}

else

{

tree[node].suf[0]+=tree[2*node].suf[1];

tree[node].suf[1]+=tree[2*node].suf[2];

tree[node].suf[2]+=tree[2*node].suf[0];

}

tree[node].count+=tree[2*node].suf[0]*tree[2*node+1].pre[0];

tree[node].count+=tree[2*node].suf[1]*tree[2*node+1].pre[2];

tree[node].count+=tree[2*node].suf[2]*tree[2*node+1].pre[1];

}

void update(int node, int st, int end,int range,long long int val)

{

if(st>end || st>range || end<range)

return ;

if(st==range && end==range)

{

arr[st]=(val)%3;;

 tree[node].suf[(arr[st])%3]=1;

 tree[node].suf[(arr[st]+1)%3]=0;

           tree[node].suf[(arr[st]+2)%3]=0;

  tree[node].pre[arr[st]%3]=1;

  tree[node].pre[(arr[st]%3+2)%3]=0;

  tree[node].pre[(arr[st]+1)%3]=0;  

        if(arr[st]%3==0)

        tree[node].count=1;

        else

        tree[node].count=0;

        tree[node].sum=(arr[st]%3);

        return ;

}

update(2*node,st,(st+end)/2,range,val);

update(2*node+1,(st+end)/2+1,end,range,val);

tree[node].count=tree[2*node].count+tree[2*node+1].count;

tree[node].sum=(tree[2*node].sum+tree[2*node+1].sum)%3;

tree[node].pre[0]=tree[2*node].pre[0];

tree[node].pre[1]=tree[2*node].pre[1];

tree[node].pre[2]=tree[2*node].pre[2];

tree[node].suf[0]=tree[2*node+1].suf[0];

tree[node].suf[1]=tree[2*node+1].suf[1];

tree[node].suf[2]=tree[2*node+1].suf[2];

    if(tree[2*node].sum%3==0)

    {

     tree[node].pre[0]+=tree[2*node+1].pre[0];

     tree[node].pre[1]+=tree[2*node+1].pre[1];

 tree[node].pre[2]+=tree[2*node+1].pre[2];

}

else if(tree[2*node].sum%3==1)

{

tree[node].pre[0]+=tree[2*node+1].pre[2];

     tree[node].pre[1]+=tree[2*node+1].pre[0];

 tree[node].pre[2]+=tree[2*node+1].pre[1];

 

}

else

{

tree[node].pre[0]+=tree[2*node+1].pre[1];

     tree[node].pre[1]+=tree[2*node+1].pre[2];

 tree[node].pre[2]+=tree[2*node+1].pre[0];

}

if(tree[2*node+1].sum==0)

{

tree[node].suf[0]+=tree[2*node].suf[0];

tree[node].suf[1]+=tree[2*node].suf[1];

tree[node].suf[2]+=tree[2*node].suf[2];

}

else if(tree[2*node+1].sum==1)

{

tree[node].suf[0]+=tree[2*node].suf[2];

tree[node].suf[1]+=tree[2*node].suf[0];

tree[node].suf[2]+=tree[2*node].suf[1];

 

}

else

{

tree[node].suf[0]+=tree[2*node].suf[1];

tree[node].suf[1]+=tree[2*node].suf[2];

tree[node].suf[2]+=tree[2*node].suf[0];

}

tree[node].count+=tree[2*node].suf[0]*tree[2*node+1].pre[0];

tree[node].count+=tree[2*node].suf[1]*tree[2*node+1].pre[2];

tree[node].count+=tree[2*node].suf[2]*tree[2*node+1].pre[1];

}

segment query(int node, int st, int end,int qs, int qe)

{

if(st>end || st>qe || end<qs)

    {

     segment temp;

     temp.count=0;

     temp.sum=0;

     temp.pre[0]=0;temp.pre[1]=0;

     temp.pre[2]=0; temp.suf[0]=0;temp.suf[1]=0;temp.suf[2]=0;

     return temp;

}

if(st>=qs && end<=qe)

{

return tree[node];

}

segment q1=query(2*node,st,(st+end)/2,qs,qe);

segment q2=query(2*node+1,(st+end)/2+1,end,qs,qe);

segment q3;

q3.count=q1.count+q2.count;

q3.sum=(q1.sum+q2.sum)%3;

q3.pre[0]=q1.pre[0];

q3.pre[1]=q1.pre[1];

q3.pre[2]=q1.pre[2];

q3.suf[0]=q2.suf[0];

q3.suf[1]=q2.suf[1];

q3.suf[2]=q2.suf[2];

    if(q1.sum%3==0)

    {

     q3.pre[0]+=q2.pre[0];

     q3.pre[1]+=q2.pre[1];

 q3.pre[2]+=q2.pre[2];

}

else if(q1.sum%3==1)

{

q3.pre[0]+=q2.pre[2];

     q3.pre[1]+=q2.pre[0];

 q3.pre[2]+=q2.pre[1];

 

}

else

{

q3.pre[0]+=q2.pre[1];

     q3.pre[1]+=q2.pre[2];

 q3.pre[2]+=q2.pre[0];

}

if(q2.sum==0)

{

q3.suf[0]+=q1.suf[0];

q3.suf[1]+=q1.suf[1];

q3.suf[2]+=q1.suf[2];

}

else if(q2.sum==1)

{

q3.suf[0]+=q1.suf[2];

q3.suf[1]+=q1.suf[0];

q3.suf[2]+=q1.suf[1];

 

}

else

{

q3.suf[0]+=q1.suf[1];

q3.suf[1]+=q1.suf[2];

q3.suf[2]+=q1.suf[0];

}

q3.count+=q1.suf[0]*q2.pre[0];

q3.count+=q1.suf[1]*q2.pre[2];

q3.count+=q1.suf[2]*q2.pre[1];

return q3;

}

char str[100010];

int main()

{

int n;

int q;

cin>>n;

cin>>q;

cin>>str;

for(int i=0;i<n;i++)

{

arr[i]=str[i]-'0';

}

build(1,0,n-1);

/* for(int i=1;i<=9;i++)

{

//  cout<<"nocd "<<" "<<i<<endl;

// cout<<"pre "<<tree[i].pre[0]<<" "<<tree[i].pre[1]<<" "<<tree[i].pre[2]<<endl;

 //cout<<" suff  "<<tree[i].suf[0]<<" "<<tree[i].suf[1]<<" "<<tree[i].suf[2]<<endl;

 cout<<i<<" "<<tree[i].count<<endl;

}*/

long long int val;int range;

while(q--)

{

int tp;

// cin>>tp;

scanf("%d",&tp);

if(tp==1)

{

 //cin>>range>>val;

 scanf("%d",&range);

 scanf("%lld",&val);

 update(1,0,n-1,range-1,val);

}

else

{

int qs,qe;

//cin>>qs>>qe;

scanf("%d %d",&qs,&qe);

segment ans;

ans=query(1,0,n-1,qs-1,qe-1);

printf("%lld\n",ans.count);

}

}

return 0;

}

******** code ends here****