RMQSQ - Range Minimum Query

no tags 

You are given a list of numbers and queries. Each query is specified by two numbers and j; the answer to each query is the minimum number between the range [i, j] (inclusive).

Note: the query ranges are specified using 0-based indexing.

Input

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number (Q <= 10,000). The next Q lines each contain two numbers i and which specify a query you must answer (0 <= i, j <= N-1).

Output

For each query, output the answer to that query on its own line in the order the queries were made.

Example

Input:
3
1 4 1
2
1 1
1 2 Output: 4
1

hide comments
linhthebest: 2022-05-19 13:03:48

+ Sprase table (0,12s, 11M): <snip>
+ Segment tree (0,13s, 11M): <snip>
[Simes]: No thanks, we don't want links to code.

Last edit: 2022-05-31 18:52:38
wlguedes: 2022-05-11 02:48:15

Also possible to solve using disjoint set union (https://cp-algorithms.com/data_structures/disjoint_set_union.html#arpa)

namvinhkhang: 2021-12-27 12:05:26

i keep getting WA on test 5 and have no ideas whats wrong
Can someone tell me ?
<snip>

[NG]: No code in comments, use forum.

Last edit: 2021-12-28 01:51:56
mr__abhilash: 2021-10-27 14:35:14

good question

shofiqur_052: 2021-10-17 19:13:09

Algo - Segment tree
Time : 0.07 s
Memory : 5.4 M

Much efficient with this algo, for both, time & memory

Last edit: 2021-10-17 19:14:22
amit2808_: 2021-09-10 08:23:01

Yeah exactly Errichto's video on sparse table is excellent. Done with sparse table.

moarvivek: 2021-07-23 15:05:08

Solved using Square Root Decomposition, Segment tree and Sparse Table.

sayang992: 2021-06-03 05:52:01

0.13 sec using sparse table and 0.07 using segment tree. Using segment tree gives better result as Q<N here. Although answering query takes O(1) in sparse table but building it takes o(nlog(n)) so overal complexity is O(nlog(n) +Q) for sparse table. But for segment tree building the tree takes O(4n) and answering each query takes O(log(n)) so overall O(n+Qlog(n)). Since Q<N so segment tree gives better time. And for space no doubt segment tree is better as it takes linear space. So my sparse table took 13 MB and segment tree only 5.3 MB. So better use segment tree if query<Size of array.

Update:- Square root decomposition took 0.11 sec and 5.4 MB.

Last edit: 2021-06-14 05:10:37
cooli0_1: 2021-05-13 18:30:10

O(nlgn) preprocessing and O(1) query time using sparse Table :D

rushi2001: 2021-05-13 14:43:40

Tried in 3 Ways .
Way Used :
1> Segment Tree - 0.09
2> Sparse Table - 0.13
3> Square-root Decomposition - 0.07

Last edit: 2021-06-27 20:55:08

Added by:Joshua Kirstein
Date:2014-10-18
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All