# Range Minimum Query

Flashcards by msladey, updated more than 1 year ago
 Created by msladey almost 6 years ago
13
0

### Description

Range Minimum Query

## Resource summary

 Question Answer Define the Range Minimum Query Problem i.e what does an RMQ return? The Range Minimum Query is the location of the smallest element in A[i,j] Describe the preprocessing for the Block Decomposition Algorithm for RMQs (Solution One) Store Ak (Where Ak is an array of length n/k so that for all i, Ak[i] = (x,v) where v is the minimum in A[ik, (i+1)k] and x is its location in A.) for all k = 1,2,4,8 ... <= n. Describe how a query is performed for the Block Decomposition Algorithm for RMQs. Find the largest block which is completely contained within the query interval, but doesn't overlap a block you have chosen before. The minimum is the smallest in these blocks. With the Block Decomposition algorithm, describe why the query time is O(logn) We pick at most 2 blocks of each size. There are O(logn) sizes. Picking the next block takes O(1) time. Therefore, we have O(logn). What is the time and space complexity for the Block Decomposition algorithm? O(n) Explain the preprocessing stage of the 'Solution 2' algorithm for RMQs. We build Rk for k = 2,4,8,16... <= n. Rk stores RMQ(i, i + k - 1) for all i. We build R2k from Rk in O(n) time. We build R2 from A in O(n) time. Therefore, preprocessing takes O(nlogn) time (logn R arrays). How much total space is used by the 'solution two' algorithm for RMQs? O(nlogn) How do we compute RMQ(i , j) if the interval length l = (j - i + 1) is not a power of two? Find the k such that k <= l <= 2k. Compute the minimum of RMQ(i, i+k-l) and RMQ(j-k+1, j). Using the 'Low Resolution RMQ' algorithm for RMQs. What time complexities can we expect? O(nloglogn) space and prep. O(1) query.

### Similar

Mathematical Preliminaries
Hamming Distance
Suffix Arrays
Suffix Trees
Data Structures & Algorithms
Data Structures & Algorithms
Computer science unit 2
Algorithms ♡
Computational Thinking ♡
Searching and Sorting Algorithms
Systems Software Revision