Proofs: Mo's algorithm

Mo's algorithm makes O(n sqrt q) moves full

This proof shows: complexity.

Let $1 \le B \le n$ be the block size, $k = \lceil n / B \rceil$ the number of blocks, and let the queries be sorted by the key $(\lfloor l / B \rfloor, r)$. Let $(l_1, r_1), \ldots, (l_q, r_q)$ be the queries in this order and $(l_0, r_0) = (0, 0)$. A round makes exactly $|l_t - l_{t-1}| + |r_t - r_{t-1}|$ calls of ADD and REMOVE, because each loop moves one end one step towards its target. So the total cost is

Lemma 1 (the right end). $\sum_t |r_t - r_{t-1}| \le 2 n k$.

Proof. Group the rounds by the block $b_t = \lfloor l_t / B \rfloor$; at most $k$ groups are non-empty. Inside a group the $r_t$ are non-decreasing, so the moves inside the group add up to at most $n$. The first round of each group moves $R$ by at most $n$. Over at most $k$ groups the sum is at most $2 n k$. $\square$

Lemma 2 (the left end). $\sum_t |l_t - l_{t-1}| \le q B + 2 n + 2 B$.

Proof. If $b_t = b_{t-1}$, both left ends lie in the same block of $B$ positions, so $|l_t - l_{t-1}| < B$, and these rounds add up to less than $q B$. Otherwise $b_t > b_{t-1}$ (with $b_0 = 0$ for the start), and $0 < l_t - l_{t-1} < (b_t - b_{t-1} + 1) B$. The blocks increase along these rounds, so the sum of $b_t - b_{t-1}$ over them is at most $k - 1$, and there are at most $k$ such rounds. They add up to less than $(k - 1 + k) B < 2 k B < 2(n + B)$, because $k B < n + B$. $\square$

Theorem. With $B = \max(1, \min(n, \lceil n / \sqrt q \rceil))$ and $1 \le q \le n^2$, the algorithm makes $O(n \sqrt q)$ calls of ADD and REMOVE, and with an $O(1)$ cost per call it runs in $O(n \sqrt q + q \log q)$ time.

Proof. By Lemmas 1 and 2, $C \le 2 n \lceil n / B \rceil + q B + 4n$. With $B \ge n / \sqrt q$, $n \lceil n / B \rceil \le n (\sqrt q + 1)$. With $B \le n / \sqrt q + 1$, $q B \le n \sqrt q + q \le 2 n \sqrt q$ because $q \le n^2$ gives $\sqrt q \le n$. So $C = O(n \sqrt q + n) = O(n \sqrt q)$. Sorting the keys takes $O(q \log q)$ time, and the other lines of the loop take $O(q)$. $\square$

The bound of Lemma 1 is tight. For each block $b$, take the two queries $(bB, bB + 1)$ and $(bB, n)$. In sorted order, $R$ climbs to $n$ in each block and falls back to $(b + 1) B + 1$ at the start of the next one, so $\sum_t |r_t - r_{t-1}| \ge \sum_{b=0}^{k-2} (n - (b + 1) B - 1)$, which is about $n k / 2$.

Mo's algorithm returns the value of each query range full

This proof shows: correctness, termination.

Let $A[0 \ldots n-1]$ be the array and $Q_0, \ldots, Q_{q-1}$ the queries, with $Q_j = (l_j, r_j)$ and $0 \le l_j \le r_j \le n$. Write $W(L, R)$ for the multiset $\{A[L], \ldots, A[R-1]\}$. The holes satisfy the contract: if $S$ is the state of $W(L, R)$, then ADD$(L - 1)$ makes it the state of $W(L - 1, R)$ for $L \ge 1$, ADD$(R)$ makes it the state of $W(L, R + 1)$ for $R < n$, REMOVE$(L)$ makes it the state of $W(L + 1, R)$ for $L < R$, REMOVE$(R - 1)$ makes it the state of $W(L, R - 1)$ for $L < R$, and ANSWER returns $f(W(L, R))$.

Invariant (I). Before each round of line L3 and after each step of lines L4 to L7, $0 \le L \le R \le n$ and $S$ is the state of $W(L, R)$.

Lemma 1. (I) holds before the first round.

Proof. Line L2 sets $L = R = 0$ and the state of the empty window, which is $W(0, 0)$. $\square$

Lemma 2. If (I) holds at the start of a round for the query $(l, r)$, then it holds after each step of lines L4 to L7, every call of ADD and REMOVE meets the contract, and at the end $L = l$ and $R = r$.

Proof. Let $(L_0, R_0)$ be the window at the start.

Line L4 runs while $L > l$. Each step has $L \ge 1$ because $L > l \ge 0$, sets $L \leftarrow L - 1$ and calls ADD on the new $L$, which is the item that enters on the left. $L$ stays at most $R$ because it decreases. The loop stops with $L = \min(L_0, l)$.

Line L5 runs while $R < r$. Each step has $R < r \le n$, calls ADD$(R)$, the item that enters on the right, and sets $R \leftarrow R + 1$. The loop stops with $R = \max(R_0, r)$.

Now $L \le l$ and $R \ge r$. Line L6 runs while $L < l$. During this loop $L < l \le r \le R$, so $L < R$ and REMOVE$(L)$ meets the contract; then $L \leftarrow L + 1 \le l \le R$. The loop stops with $L = l$.

Line L7 runs while $R > r$. During this loop $R > r \ge l = L$, so $L < R$, the step sets $R \leftarrow R - 1$ and REMOVE removes $A[R]$, the last item of the old window, and $R \ge r \ge L$ afterwards. The loop stops with $R = r$.

Each step keeps (I) by the contract of the hole it calls. $\square$

Theorem 1 (correctness). For each $j$, $\mathrm{ans}[j] = f(A[l_j \ldots r_j - 1])$.

Proof. Line L1 lists every index $j$ exactly once, because it sorts a permutation. By Lemma 1 and Lemma 2, by induction over the rounds, (I) holds at line L8 of the round of $j$ with $[L, R) = [l_j, r_j)$. So ANSWER returns $f(W(l_j, r_j))$, and line L8 stores it at index $j$. Later rounds write only other indices. $\square$

Theorem 2 (termination). The algorithm stops after a finite number of calls of ADD and REMOVE.

Proof. Each of the four loops of a round changes one end by one step towards a fixed target and stops when the target is reached, so a round makes at most $|L_0 - l| + |R_0 - r| + |l - L_0| + |r - R_0| \le 4n$ calls. There are $q$ rounds. $\square$

Remark (the order of the loops). The proof of Lemma 2 uses that lines L4 and L5 run before lines L6 and L7. If the left end shrinks first, for example from $[0, 2)$ to the query $[5, 8)$, then $L$ passes $R$, and REMOVE is called on items that are not in the window, which breaks the contract.