#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/mo-s-algorithm-framework

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/mo-s-algorithm-framework

Repovive

MO's Algorithm - Framework - Sqrt Decomposition | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

MO's Algorithm - Framework

The template

Here's the MO's algorithm structure:

function moAlgorithm(arr, queries)
 B := floor(sqrt(n))
 sort queries by (floor(l / B), r)

 currentL := 0
 currentR := -1
 currentAnswer := initial value

 for each query (l, r, queryIndex)
 // Expand/shrink to reach [l, r]
 while currentR < r
 currentR := currentR + 1
 add(arr[currentR])
 while currentL > l
 currentL := currentL - 1
 add(arr[currentL])
 while currentR > r
 remove(arr[currentR])
 currentR := currentR - 1
 while currentL < l
 remove(arr[currentL])
 currentL := currentL + 1

 answers[queryIndex] := currentAnswer

 return answers

You implement $add$ and $remove$ based on what you're computing.