2
$\begingroup$

MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing difficulty to understand MO'S algorithm with updates (https://www.youtube.com/watch?v=gUpfwVRXhNY)

Since articles related to MO'S algorithm with updates is rare can someone who knows this algorithm can explain it.

$\endgroup$
3
$\begingroup$

A short (or long?) recall: Mo's algorithm is used for problems, when you want to answer a lot of range queries over an array, in which it is not possible to generate an efficient data structure like a Segment tree, because combining multiple nodes can be very inefficient. The famous problem is to count the number of distinct elements in ranges $(l, r)$. Precomputing some ranges, like in a Segment tree, would not help, because combining two ranges is not efficient, and in general is an $\Omega(n)$ operation.

To answer such queries efficient, we need two ideas:

  • Mo's algorithm uses the fact that we know all queries at the start, so we can answer them offline (in any order we like). We order the range queries by the tuple $\left(\left\lfloor\frac{l}{B}\right\rfloor, r\right)$ with $B = \sqrt{n}$ and compute the answers for them in this order. This means we split the array into $\sqrt{n}$ blocks of size $\sqrt{n}$. First answer all range queries that start in the first block (sorted by their range ends), then all range queries that start in the second block, an so further.

  • The second idea is to use a data structure that represents a specific range $[L, R]$, can give us the answer to its range quickly, and it's possible to add/remove single numbers quickly to modify it's range. And we will maintain this data structure the entire time, starting with the empty range $[0, 0)$.

E.g. in the example we just use a set together with the information how often each number appears in the current range. Adding a number will increases the count of the number (or adds the number with count 1 if it doesn't exit), and removing a number just decreases the count (or removes the number from the set). Assuming that the data structure currently maintains the range $[L, R]$, and the next query covers the range $[l, r]$. Then we just need to individually add the parts of the array, that were not covered by the old range but are covered in the new range, to the data structure: $[l, r] / [L, R]$, and remove the parts that were covered before and are now not covered $[L, R] / [l, r]$. It can be easily be proven, that we only add/remove $\sqrt{n}$ numbers on average per query (if we assume that we have $Q \approx n$ queries).


To handle updates we have to handle a new dimension: time. Because an identically query $(l, r)$ asked multiple times, can give different answers depending on the updates in the time between them. So we represent each query as a tuple $(l, r, t)$. The first query gets $t = 1$, the second $t = 2$, and so on.

Again as before, we just order the queries, this time by $\left(\left\lfloor\frac{l}{B}\right\rfloor, \left\lfloor\frac{r}{B}\right\rfloor, t\right)$ with $B = n^{\frac{2}{3}}$. So here we have blocks of size $B$ for $l$ and $r$, and answer them accordingly. First all with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 0$ (sorted by $t$), then all queries with $\left\lfloor\frac{l}{B}\right\rfloor = 0$ and $\left\lfloor\frac{r}{B}\right\rfloor = 1$ (sorted by $t$), and so on.

But now, if the data structure currently represents the range $[L, R]$ at timepoint $T$, and we want to answer the query $[l, r]$ at timepoint $t$, then we additionally to adding the parts $[l, r] / [L, R]$ and removing the parts $[L, R] / [l, r]$, perform the updates in the time range $(T, t]$ if $T < t$, or undo the updates in reverse if $T > t$. It can be proven, that we add/remove/update $n^{\frac{2}{3}}$ numbers on average during each query.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy