This work studies the problem of 2-dimensional searching for the 3-sided range query of the form @math in both main and external memory, by considering a variety of input distributions. We present three sets of solutions each of which examines the 3-sided problem in both RAM and I O model respectively. The presented data structures are deterministic and the expectation is with respect to the input distribution.
In the RAM model, the only dynamic sublogarithmic bounds for this problem are due to Willard @cite_25 who attains @math worst case or @math randomized update time and @math query time using linear space. This solution poses no assumptions on the input distribution.
@cite_25
2041550253
This article illustrates several examples of computer science problems whose performance can be improved with the use of either the fusion trees [Fredman and Willard, J. Comput. System Sci., 47 (1993), pp. 424--436; Fredman and Willard, J. Comput. System Sci., 48 (1994), pp. 533--551] or one of several recent improvements to this data structure. It is likely that many other data structures can also have their performance improved with fusion trees. The examples here are only illustrative.