Improved Algorithms for the Range Next Value Problem and Applications

Costas S. Iliopoulos, Maxime Crochemore, Marcin Kubica, M. Sohel Rahman & Tomasz Walen
The Range Next Value problem (Problem RNV) is a recent interesting variant of the range search problems, where the query is for the immediate next (or equal) value of a given number within a given interval of an array. Problem RNV was introduced and studied very recently by Crochemore et. al [Finding Patterns In Given Intervals, MFCS 2007]. In this paper, we present improved algorithms for Problem RNV. We also show how this problem can...