Using persistent data structures for adding range restrictions to searching problems

Abstract

The problem of adding range restrictions to decomposable searching problems is considered. First, a general technique is given that makes an arbitrary dynamic data structure partially persistent. Then, a general technique is given that transforms a partially persistent data structure that solves a decomposable searching problem into a structure or the same problem with added range restrictions. Applying the general technique to specific searching problems gives efficient data structures, especially in case more than one range restriction, one of which has constant width, is added.