Mo's Algorithm (Range Query)
Learn Mo's Algorithm (Range Query) (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Mo's Algorithm: Offline Range Queries Some queries, such as "how many distinct values are in a[l..r]?" , cannot be combined from smaller blocks. Mo's algorithm answers them offline (all queries known in advance) by sorting them cleverly and sliding one window [L, R] across the array, adding or removing one element at a time and keeping the answer up to date. Sort queries by block of l (block size about √n), then by r. The window moves O(n√n) steps in total, so q queries cost about O((n + q)√n) .