Add MO’s Algorithm (Query Square Root Decomposition)

[Aum-Patel1234]

What would you like to Propose?

To add Mo's Algorithm, a technique for efficient range queries on arrays, to the repository. It divides the array into blocks, sorts queries based on blocks, and achieves a time complexity of O((N + Q) * sqrt(N)). This algorithm is valuable for sum queries and static data scenarios.

Issue details

Mo's Algorithm (Query Square Root Decomposition)

Mo's Algorithm is an efficient technique for answering range queries on arrays, especially useful when dealing with static array content. It divides the array into blocks and processes queries efficiently by adjusting the current range.

Explanation

• Algorithm Overview: Mo's Algorithm divides the array into blocks of equal size (usually the square root of the array size). It then sorts the queries based on the blocks they belong to and processes them in sorted order.

• Block Processing: For each query, Mo's Algorithm adjusts the current range to match the query range efficiently. It moves the current range to the right or left as needed, minimizing unnecessary recalculations.

• Efficiency: Mo's Algorithm achieves a time complexity of O((N + Q) * sqrt(N)), where N is the size of the array and Q is the number of queries. This makes it suitable for handling large datasets efficiently.

Use Cases

• Sum Queries: Mo's Algorithm is commonly used for sum queries, where the goal is to compute the sum of elements in a given range.

• Static Data: Mo's Algorithm works well with static array content, meaning that the array does not change between queries.

Example

Suppose we have an array [1, 3, 5, 2, 7, 6, 3, 1, 4, 8] and the following queries:

• Query 1: Sum of elements from index 0 to 4
• Query 2: Sum of elements from index 1 to 3
• Query 3: Sum of elements from index 2 to 7

Mo's Algorithm efficiently computes the results for these queries by dividing the array into blocks and adjusting the current range as needed.

Conclusion

Mo's Algorithm is a powerful technique for answering range queries on arrays. Its efficiency and versatility make it a valuable tool for various applications, including competitive programming and data analysis.

This is a new algorithm I suggest, I have implemented it, so please allow me to add it to this repo.

Thank You
(I am new to GitHub, so please excuse me if I am unclear on my issue. This is the first issue I have raised.)

Additional Information

No response

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!