Range Maximum Query

Problem definition

There are several approaches to range maximum query, with different complexities in speed and storage, and preprocessing, as explained next. Your mission is to pick one of them for your implementation to meet the requirement of this assignment. (We will briefly review these methods in class.)

• straightforward search: Run a loop from $l$ to $u$ and find the maximum in the given range.
  • Query: $O(n)$
  • Memory: $O(1)$
  • Preprocess: $O(1)$
• Naive method: Create a matrix B where B[i,j] stores the maximum within $\{a_i, a_{i+1}, ..., a_j\}$.
  • Query: $O(1)$
  • Memory: $O(n^2)$
  • Preprocess: $O(n^2)$
• Square root decomposition: Split the array into $\sqrt{n}$ subarrays of size $\sqrt{n}$ and precompute the maximum of each subarray.
  • Query: $O(\sqrt{n})$
  • Memory: $O(\sqrt{n})$
  • Preprocess: $O(n)$
• Iterative doubling (or sparse table algorithm): Precompute the maximum of each subarray of length $2^k$. Note that the range $[l,u]$ can be expressed as $[l,l+2^k-1]\cup[u-2^k+1, u]$ for a certain value of $k$.
  • Query: $O(1)$
  • Memory: $O(n\log n)$
  • Preprocess: $O(n\log n)$
• Segment tree: Precompute the maximum of the entire array. Split the array into two subarrays and recurse.
  • Query: $O(\log n)$
  • Memory: $O(n)$
  • Preprocess: $O(n)$

• Wikipedia: 4 methods
• Range Minimum Query (Square Root Decomposition and Sparse Table): Simple solution, square root decomposition, sparse table algorithm
• Range Minimum Query: Segment trees
• Sequence 資料結構: Array / List: sparse table algorithm

I/O formats

• Input format
  • The first line of the input contains two integers, $n$ (length of the array) and $m$ (number of queries), with $1\leq n, m \leq 100000$.
  • The second line contains $n$ integers, $a_1, a_2, ..., a_{n}$, with $0 \leq a_i \leq 10^9$.
  • Each of the following $m$ lines contains two integers, $l_i$ and $u_i$, which are the lower and upper indices for the $i$th query.
• Output format
  • Print one integer for each query.
• Example

  Input:

  5 3 10 30 50 20 40 1 5 1 2 4 5

  Output:

  50 30 40

Test cases

1. n=5. m=3 ==> input, output
2. n=100000. m=100000 ==> input, output

Requirements

• Limits
  • Time limit: 1 second.
  • Memory limit: 256MB. (This may preclude the use of the naive method which requires $O(n^2)$ memory.)
• You need to use max() in STL. (So you need to put "#include <algorithm>" in your code.)

Submission guidelines

Side notes

• Be aware that our description of indexing here is 1-based, while the indexing of C/C++ is 0-based.
• In practice, range maximum query returns the position instead of the element.
• As usual...
  1. Your program should take the input from the standard input and send the output to the standard output. That is, you should be able to redirect the input/output files like this: myProgram < input.txt > output.txt
  2. You need to write the program from scratch. You cannot use any open-source or readily available solvers.