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.
Also read, Euclid GCD Algorithm
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;
}
ll Answer;
/* 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)
{
Answer-=ager;
}
COUNT[vv]++;
if(COUNT[vv]==1)
{
Answer+=akn;
}
}
}
/* This is used for addition of new terms */
void Add(int i)
{
int vv=ARRAY[i];
ll pp=Mapping_a[vv];
COUNT[vv]++;
if(COUNT[vv]==1)
Answer+=pp;
}
/* For removing an element */
void Remove(int i)
{
int vv=ARRAY[i];
ll pp=Mapping_a[vv];
COUNT[vv]--;
if(COUNT[vv]==0)
Answer-=pp;
}
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;
Answer=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--;
Add(LEFT_TIMER);
}
while(RIGHT_TIMER<y)
{
RIGHT_TIMER++;
Add(RIGHT_TIMER);
}
while(RIGHT_TIMER>y)
{
Remove(RIGHT_TIMER);
RIGHT_TIMER--;
}
FINAL_ANS_ARRAY[query[i].second.second]=Answer;
}
/* printing the answers */
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 2Output
3
4Complexities
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
305+ registered