## 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:

This editorial will not go through specific implementation details.

Let be the number of queries.

##### Subtask 1

Check all elements in the submatrix.

**Time Complexity:**

**Memory Complexity:**

##### Subtask 2

Build segment trees.

**Time Complexity:**

**Memory Complexity:**

##### Subtask 2 Alternative Solution

Build sparse tables.

**Time Complexity:**

**Memory Complexity:**

##### Subtask 3

Build a -dimensional segment tree.

**Time Complexity:**

**Memory Complexity:**

##### Subtask 4

Build a -dimensional sparse table.

**Time Complexity:**

**Memory Complexity:**

##### Fun Solution

There are ways to abuse the randomness of the data.

## Comments