CONSTANT-TIME RMESH ALGORITHMS FOR THE RANGE MINIMA AND CO-MINIMA PROBLEMS

We present efficient solutions on an RMESH for the following two probl ems: (i) The range minima problem: Given an array of real numbers, A = (a(1),...,a(n)), preprocess A so that, after preprocessing, for any t wo query indices 1 less than or equal to i less than or equal to j les s than or equal to n, min {a(i),...,a(j)} can be found efficiently. (i i) The range co-minima problem: Given an array of positive integers, B = (b(1),...,b(n)) with b(i) less than or equal to n for all i, prepro cess B so that, after preprocessing, for any two query indices 1 less than or equal to i less than or equal to j less than or equal to n, th e minimum positive integer not in (b(i),...,b(j)) can be found efficie ntly. In other words, min {{1,2,...,n + 1} - {b(i),...,b(j)}} is to be found. Our preprocessing algorithms for both problems take constant t ime on an n x n RMESH, and a query can be answered in constant time us ing a single processor. (C) 1998 Elsevier Science B.V. All rights rese rved.