1.
Introduction
2.
2.1.
Implementation
2.1.1.
Input
2.1.2.
Output
2.2.
Complexities
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Mo's Algorithm With Updates (SUM query)

Saksham Gupta
0 upvote

## Introduction

If you are into sports, then competitive programming is definitely for you; the only difference here is that it is more of a mind sport where you have to solve complex problems using complex algorithms. Today, we will discuss variation one such algorithm, i.e., Mo's Algorithm, and see how we can work with Mo's algorithm with updates.

Before going into detail about how updates work with Mo's Algorithm, let's first recall what Mo's algorithm is.

Mo's algorithm takes advantage of the fact that the queries are already given to us beforehand, allowing us to respond to them offline (in any order we like). The range queries are ordered by the tuple ([L/B], R) with B= sqrt(N), B is the size of one block, and the answers are calculated in that order. This means the array is divided into sqrt(N) blocks of size sqrt(N). We first find out answers to all range questions that begin with the first block (sorted by range ends), then we will move to all the queries that are inside the second block and so on.

But how are we gonna add an update function in this?
We now have to deal with a new dimension: time in order to handle updates. Because the answers to the same query (L, R) asked numerous times can differ depending on the updates in the time between them. As a result, each query is represented as a tuple (L, R, t). t for the first query is 1, for the second is 2, and so on.

We will sort the queries by ([L/B], [R/B], t) with B=n ^ (2/3), as we did before.Now, All queries with [L/B] = 0 and [R/B] = 0 (sorted by t) come first, followed by all queries with [L/B] = 0 and [R/B] = 1 (sorted by t), and so on.

However, if the data structure now represents the range [L', R'] at timepoint T and we want to answer the query [L, R] at time point t, we must add the parts [L, R]/[L', R'] and remove the parts [L', R']/[L, R], conduct the updates in the time range (T,t) if T < t, or reverse the modifications if T > t.

Now let's understand this better by the implementation of the problem in which we have to solve the range sum query problem along with updation.

### Implementation

``````#include <bits/stdc++.h>
#define ll long long int

using namespace std;
int n,block;
ll ARRAY[50005],Mapping_a[1000005],COUNT[1000005],FINAL_ANS_ARRAY[100005];
vector< pair< pair<ll,int> ,int> >Temp_Array;
pair<int, int> Updation_Array[50005];
vector< pair< pair<int, int> , pair<int, int> > >query;
map<ll,ll>mm;

/* Compression Function */
void Comp()
{

sort(Temp_Array.begin(),Temp_Array.end());

/* Looping over sorted array*/
for(int i=0;i<Temp_Array.size();i++)

{
/* If its zero */
if(Temp_Array[i].second==0)
{
ll val=Temp_Array[i].first.first;
if(mm[val]==0)
{
mm[val]=i+1;
}

/* Updating value */
ARRAY[Temp_Array[i].first.second]=mm[val];
Mapping_a[ARRAY[Temp_Array[i].first.second]]=val;
}
else
{
ll val=Temp_Array[i].first.first;
if(mm[val]==0)
{
mm[val]=i+1;
}
Updation_Array[Temp_Array[i].first.second].second=mm[val];
Mapping_a[Updation_Array[Temp_Array[i].first.second].second]=val;
}
}
}

/* Comparator function for soRIGHT_TIMERing */
bool comparator(pair< pair<int, int> , pair<int, int> >x,pair< pair<int, int> , pair<int, int> >y)
{
int p=x.first.first/block;
int q=y.first.first/block;

/* If both of them are equal */
if(p==q)
{
int pp=x.first.second/block;
int qq=y.first.second/block;
if(pp==qq)
{
return x.second.first<y.second.first;
}
return x.first.second<y.first.second;
}
return x.first.first<y.first.first;
}

/* This will help us in updation */
void update(int i,int x,int y)
{
int IDX=Updation_Array[i].first;
int vv=Updation_Array[i].second;

int old=ARRAY[IDX];
ARRAY[IDX]=vv;
Updation_Array[i].second=old;

if(IDX>=x && IDX<=y)
{
ll ager=Mapping_a[old];
ll akn=Mapping_a[vv];
COUNT[old]--;
if(COUNT[old]==0)
{
}
COUNT[vv]++;
if(COUNT[vv]==1)
{
}
}
}

/* This is used for addition of new terms */
{
int vv=ARRAY[i];
ll pp=Mapping_a[vv];
COUNT[vv]++;
if(COUNT[vv]==1)
}
/* For removing an element */
void Remove(int i)
{
int vv=ARRAY[i];
ll pp=Mapping_a[vv];
COUNT[vv]--;
if(COUNT[vv]==0)
}
int main()
{
int t,cas=0;

/* Input */
cin>>n;
for(int i=0;i<n;i++)
{
cin>>ARRAY[i+1];

Temp_Array.push_back(make_pair(make_pair(ARRAY[i+1],i+1),0));
}
int q;
cin>>q;
int COUNTt=0;

/* Query Input */
for(int i=0;i<q;i++)
{
getchar();
int x,y;
char c;
cin>>c>>x>>y;
if(c=='U')
{
Updation_Array[++COUNTt]=make_pair(x,y);
Temp_Array.push_back(make_pair(make_pair(y,COUNTt),1));
}
else
{
query.push_back(make_pair(make_pair(x,y),make_pair(COUNTt,i)));
}
}

Comp();

block=sqrt(n);

sort(query.begin(),query.end(),comparator);

int LEFT_TIMER=1,RIGHT_TIMER=0,update_TIMER=0;
memset(FINAL_ANS_ARRAY, -1, sizeof(FINAL_ANS_ARRAY));
for(int i=0;i<query.size();i++)
{
int x=query[i].first.first;
int y=query[i].first.second;
int tt=query[i].second.first;

/* Untill the current time is less than tt*/
while(update_TIMER<tt)
{
update_TIMER++;
update(update_TIMER,LEFT_TIMER,RIGHT_TIMER);
}

/* Untill the current time is greater than tt*/
while(update_TIMER>tt)
{
update(update_TIMER,LEFT_TIMER,RIGHT_TIMER);
update_TIMER--;
}
while(LEFT_TIMER<x)
{
Remove(LEFT_TIMER);
LEFT_TIMER++;
}
while(LEFT_TIMER>x)
{
LEFT_TIMER--;
}
while(RIGHT_TIMER<y)
{
RIGHT_TIMER++;
}
while(RIGHT_TIMER>y)
{
Remove(RIGHT_TIMER);
RIGHT_TIMER--;
}
}

for(int i=0;i<q;i++)
{
if(FINAL_ANS_ARRAY[i]==-1)
continue;
cout<<FINAL_ANS_ARRAY[i]<<endl;
}
return  0;

}``````

#### Input

``````3
1 2 3
3
A 0 2
U 0 2
A 0 2``````

#### Output

``````3
4``````

### Complexities

#### Time Complexity

O(Q * (B + (N/B) ^ 2)), where â€˜Nâ€™ is the size of array and â€˜Qâ€™ is the number of queries and â€˜Bâ€™ is the size of the block.

Reason: We are traversing over Q queries, and each time we first loop over the block of size â€˜Bâ€™ and, along with it, perform calculations which in worst case costs O((N/B) ^ 2) time. Thus, the overall time complexity is O(Q * B) + O(Q * (N/B) ^ 2) ~ O(Q * (B + (N/B) ^ 2).

#### Space Complexity

O(1)

Reason: We are not using any external space.

Check out this array problem - Merge 2 Sorted Arrays

## FAQs

1. What is meant by Moâ€™s Algorithm?
Mo's method keeps track using one data structure and only performs simple and quick operations on it. The concept is to respond to questions in a specific order based on the indexes. All queries with the left index in block 0 will be answered first, followed by queries with the left index in block 1, and so on.

2. What types of problems can be solved using Moâ€™s Algorithm?
When there are many range queries on an array and changes to the array's elements, we can use it. This strategy should be used only when the number of update operations exceeds the number of query range operations; otherwise, segment trees can be used.

3. What is a segment tree?
A segment tree, also known as a statistic tree, is a data structure that stores information about intervals or segments. It allows you to see which segments in the database contain a specific point.

4. What types of problems can be solved using segment trees?
A large number of problems can be solved using segment trees, but segment trees are most used to solve problems in which we have to solve min, max, or sum queries of a given range.

5. Is there any other Data Structures and Algorithms content in Coding Ninjas Studio?
Yes, Coding Ninjas Studio allows you to practice coding as well as answer frequently asked interview questions. The more we practice, the more likely we are to acquire a job at our dream company.

## Key Takeaways

We saw how we could solve range query problems using Moâ€™s algorithm  and solved the problem â€˜Sum Range Query with Updation',.Some other problems that revolve around the Range query concepts are Range minimum queryMatrix range query, etc. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!

Live masterclass