Mo's Algorithm - Introduction

Hello everyone !

Welcome back to my blog .

Today , we will be learning about Mo's Algorithm's introduction via a simple problem .

In this problem we are given an array of n numbers and then we are given q queries consiting of l and r and we need to find the sum of elements from l to r.

We could do this naively , by just summing up all elements from l to r and then printing this .

But the time complexity of this naive method would be O(m*q) .

But what if we played smartly , we are given all queries so why not pre process them .

So , let us sort the queries into blocks with l in the range 0 to root(n) then to 2*root(n) and so on .

And in each block , let us sort the queries with r.

Then we iterate over all the queries and we subtract the elements not required and add the elements required from the previous sum thus reducing our work .

The time complexity of this program would be O((n+q)*root(n)) , which is quite better than before .

This time complexity can be found out easily by computing the number of movements of the left and right cursors in recomputing the sum .

Do take a look at the below C++ code for better understanding :-

Code :-

// Program to compute sum of ranges for different range

// queries

#include <bits/stdc++.h>

using namespace std;

  

// Variable to represent block size. This is made global

// so compare() of sort can use it.

int block;

  

// Structure to represent a query range

struct Query

{

    int L, R;

};

  

// Function used to sort all queries so that all queries 

// of the same block are arranged together and within a block,

// queries are sorted in increasing order of R values.

bool compare(Query x, Query y)

{

    // Different blocks, sort by block.

    if (x.L/block != y.L/block)

        return x.L/block < y.L/block;

  

    // Same block, sort by R value

    return x.R < y.R;

}

  

// Prints sum of all query ranges. m is number of queries

// n is size of array a[].

void queryResults(int a[], int n, Query q[], int m)

{

    // Find block size

    block = (int)sqrt(n);

  

    // Sort all queries so that queries of same blocks

    // are arranged together.

    sort(q, q + m, compare);

  

    // Initialize current L, current R and current sum

    int currL = 0, currR = 0;

    int currSum = 0;

  

    // Traverse through all queries

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

    {

        // L and R values of current range

        int L = q[i].L, R = q[i].R;

  

        // Remove extra elements of previous range. For

        // example if previous range is [0, 3] and current

        // range is [2, 5], then a[0] and a[1] are subtracted

        while (currL < L)

        {

            currSum -= a[currL];

            currL++;

        }

  

        // Add Elements of current Range

        while (currL > L)

        {

            currSum += a[currL-1];

            currL--;

        }

        while (currR <= R)

        {

            currSum += a[currR];

            currR++;

        }

  

        // Remove elements of previous range.  For example

        // when previous range is [0, 10] and current range

        // is [3, 8], then a[9] and a[10] are subtracted

        while (currR > R+1)

        {

            currSum -= a[currR-1];

            currR--;

        }

  

        // Print sum of current range

        cout << "Sum of [" << L << ", " << R

             << "] is "  << currSum << endl;

    }

}

  

// Driver program

int main()

{

    int a[] = {1, 1, 2, 1, 3, 4, 5, 2, 8};

    int n = sizeof(a)/sizeof(a[0]);

    Query q[] = {{0, 4}, {1, 3}, {2, 4}};

    int m = sizeof(q)/sizeof(q[0]);

    queryResults(a, n, q, m);

    return 0;

}










Thanks to Ruchir Garg(Geek for geeks) for contributing the code .




For any doubts or queries , contact me or leave them in the comments section .