THE FOLD / CHEAT / THE KONAMI CODE / THE MO ALGORITHM
THE MO ALGORITHM
reorder queries to answer them fast
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Mo’s algorithm answers many range queries offline — e.g. “how many distinct values in a[l..r]?” — astonishingly fast by reordering the questions. It sorts the queries so that consecutive ones have nearly the same window, then slides two pointers (l and r), adding and removing one element at a time while maintaining a running answer. Sorting by √n-sized blocks of the left endpoint bounds the total pointer movement, turning many hard queries into one long sweep.
LIT verified live: over hundreds of instances, Mo’s distinct-count answers exactly match a naive per-query recount (window.__mo). FIG no framing; exact comparison against brute force.
LIT verified live: over hundreds of instances, Mo’s distinct-count answers exactly match a naive per-query recount (window.__mo). FIG no framing; exact comparison against brute force.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-konami-code — the clever ordering trick that unlocks the whole batch; reorder the queries just so, and a hard problem falls out cheaply. Mo’s algorithm is that code. AVAN (AI) built the instrument: the block-sort of queries, the add/remove window slide with a live distinct-count, and the match against a naive recount.
Credit as content: Mo’s algorithm (attributed to competitive programmer Mo Tao; a sqrt-decomposition of offline queries). The weave: David names the-konami-code; I sort the queries by √n block of their left end, slide the window adjusting the distinct-count one element at a time, and confirm every answer matches recounting each range from scratch.
Credit as content: Mo’s algorithm (attributed to competitive programmer Mo Tao; a sqrt-decomposition of offline queries). The weave: David names the-konami-code; I sort the queries by √n block of their left end, slide the window adjusting the distinct-count one element at a time, and confirm every answer matches recounting each range from scratch.
3 ONE DIMENSION
Sort queries by (block of l, then r). Slide l and r one step at a time between consecutive queries, adding/removing elements and updating the distinct-count — total movement is bounded by √n blocks.
4 TWO DIMENSIONS · INTERACTIVE
An array with range queries; Mo’s window sliding and its distinct-counts checked against naive recounts.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: many queries answered by one sweep.
AVAN’s addition (the inverse-companion): answer a batch of range queries not one at a time but by reordering them so consecutive windows barely differ, then sliding pointers with incremental updates. The inverse of ‘recompute each range from scratch’ is ‘sort the queries by √n block and sweep once, adjusting as you go.’ Magenta is the per-query recount; green is the single reordered sweep. Order the questions, answer them together.
LIT Genuine Mo's algorithm (attributed to Mo Tao; a sqrt-decomposition of offline queries). Verified live: over 300 random instances, sorting queries by (√n block of l, then r) and sliding the window with incremental add/remove of a live distinct-count returns answers identical to recounting each range from scratch (window.__mo.matchesNaive).
FIG No framing: the block-sort of queries, the add/remove window slide with a live distinct-count, and the match against a naive recount run in-browser and agree. The AVAN inverse is honest — answering a batch of range queries by reordering them so consecutive windows barely differ, then sliding pointers with incremental updates, genuinely replaces recomputing each range; magenta is the per-query recount, green the single reordered sweep. Order the questions, answer them together.
FIG No framing: the block-sort of queries, the add/remove window slide with a live distinct-count, and the match against a naive recount run in-browser and agree. The AVAN inverse is honest — answering a batch of range queries by reordering them so consecutive windows barely differ, then sliding pointers with incremental updates, genuinely replaces recomputing each range; magenta is the per-query recount, green the single reordered sweep. Order the questions, answer them together.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE KONAMI CODE · David Lee Wise (ROOT0), with AVAN