Editorial for 2-Dimensional Range Minimum Query

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

This editorial will not go through specific implementation details.

Let Q be the number of queries.

Subtask 1

Check all elements in the submatrix.

Time Complexity: \mathcal O(Q \cdot N^2)
Memory Complexity: \mathcal O(N^2)

Subtask 2

Build N segment trees.

Time Complexity: \mathcal O(N^2 + Q \cdot N \cdot \log N)
Memory Complexity: \mathcal O(N^2)

Subtask 2 Alternative Solution

Build N sparse tables.

Time Complexity: \mathcal O(N^2 \cdot \log N + Q \cdot N)
Memory Complexity: \mathcal O(N^2 \cdot \log N)

Subtask 3

Build a 2-dimensional segment tree.

Time Complexity: \mathcal O(N^2 + Q \cdot \log^2 N)
Memory Complexity: \mathcal O(N^2)

Subtask 4

Build a 2-dimensional sparse table.

Time Complexity: \mathcal O(N^2 \cdot \log^2 N + Q)
Memory Complexity: \mathcal O(N^2 \cdot \log^2 N)

Fun Solution

There are ways to abuse the randomness of the data.


There are no comments at the moment.