MO’s Algorithm (Query square root decomposition)

Explanation

- **Mo’s Algorithm** is a square root decomposition technique for answering range queries efficiently. It is commonly used for problems involving range queries, like finding the count of distinct elements in a range or answering range sum queries.

-

• Steps

  • Divide the array into blocks of size √n.
  • Sort the queries based on block number and right endpoint.
  • Process the queries by adjusting the left and right pointers of the current range and answering the query as you move the pointers.
  • Maintain a frequency array or other data structure to handle the query efficiently.

• Time Complexity

  • Time complexity: O((n + q) * √n), where n is the number of elements and q is the number of queries.