Mo's Algorithm

In Mos algorithm, we sort the queries
For ex:

Input : The following are Queries. The starting indices and ending indices are as follows

2 4

6 8

0 2

3 5

2 3

Output: After Sorting the Queries become as shown below.  

0 2

2 3

2 4

3 5

6 8

Since There are 9 elements. Square root of 9 is 3. Hence the Block Size is 3

indices 0,1,2 belong to first block where first block stores sum of the elements at these indices. In Mo's algorithm, the result of previous query is used in the calculation of next query

=========================================================================================================================

Mos algorithm to solve range sum queries

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

int bs=174;//block_size is 174 if n can take maximum of 30010

struct query

{

  int l,r,index;

};

bool cmp(query f,query s)//acts just like group by in SQL

{

    if(f.l/bs != s.l/bs) //if they dont belong to same block as l/bs gives block number 

        return f.l/bs < s.l/bs;

    return f.r<s.r; // same block sort by r value

}

int main() 

{

  int a[] ={1,5,2,4,6,1,3,5,7},n=9;  

  bs=sqrt(n); //block_size

  int noq,ad,b_id;

  cin>>noq;

  struct query q[noq];

  for(int k=0;k<noq; k++)

{

      scanf("%d%d",&q[k].l,&q[k].r);

      q[k].index=k;

  }

    // l--;r--;     

  sort(q,q+noq,cmp);

  int sum=0,cr=0,cl=0,ans[noq];

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

  {

    int left=q[i].l,right=q[i].r;

    while(cl<left)

    {

        sum=sum-a[cl];

        cl++;

    }

    while(cl>left)

    {

        sum=sum+a[cl];

        cl--;

    }

    while(cr<=right)

    {

        sum=sum+a[cr];

        cr++;

    }

    while(cr>right+1)

    {

        sum=sum-a[cr-1];

        cr--;    

    }

    ans[q[i].index]=sum;

   // cout<<sum<<endl;

  

  }

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

        cout<<ans[i]<<endl;

  return 0;

}

input:

5

2 4

6 8

0 2

3 5

2 3

output:

12

15

8

11

6