Constant-time RMESH algorithms for the range minima and co-minima problems

摘要

We present efficient solutions on an RMESH for the following two problems:(i)The range minima problem: Given an array of real numbers, A =(a_1,..., a_n)preprocess A so that, after preprocessing, for any two query indices 1≤i≤j≤n, min{a_i,..., a_j}can be found efficiently. (ii)The range co-minima problem: Given an array of positive integers, B=(b_1,..., b_n)with b_i≤n for all i, preprocess B so that, after preprocessing, for any two query indices 1≤i≤j≤n, the minimum positive integer not in{b_i,...,b_j}can be found efficiently.