General methods for adding range restrictions to decomposable searching problems

In this paper we consider the problem of adding range restrictions to decomposable searching problems. Two classes of structures for this problem are described. The first class consists of structures that use little storage and preprocessing time but still have reasonable query time. The second class consists of structures that have a much better query time, at the cost of an increase in the amount of storage and preprocessing time. Both classes of structures can be tuned to obtain different trade-offs. First we only describe static structures. To dynamize the structures a new type of weight-balanced multiway tree (the MWB-iree) is introduced that is used as an underlying structure. The MWB-tree might be useful in other applications as well