[MUSIC] Before we develop a method for solving the range query problem in the plane, let us examine the one dimensional case. Thus, the set P, is now a set of one dimensional points or real values, and the query range x,x prime represents an interval of the real line. Our question is, which points from P fall inside the interval x,x prime? In our example, you now see on the left, the query range is highlighted in red, and the three points of presenting the answer to our question are highlighted in blue. A simple way to solve this problem is the following. Let us draw the points, or values, from P, in a sorted array A. Further, to process a query range, x,x prime, let us localize both values x, and x prime in A through a binary search, and then, report all the points lying in between. Query processing time will then be logarithm n. This approach is really nice but unfortunately, it does not generalize to the two-dimensional case. Because of that, to store the points from P, we will use a binary balanced search tree rather than an array. Let us briefly recall what a binary balanced search tree is. Consider a simple set of four dimensional points, 3, 7, 11, 16, 23, 30, and 42. The binary balanced search tree for this set is depicted in the left on this slide. The leaves of this tree strongly varies from P, and for each external node, the foreign property holds. All the values stored in this left subtree are smaller, or equal to those stored in the right subtree. In addition, and in the node itself stored the value, which the maximum value from its left subtree It will be used to guide the source in the tree. Now, let us consider a query interval x,x prime. To process this query, we will search in the tree t for the vertex x, and x prime. Let mu and mu prime denote the two leaves of the tree, at which the search ends respectively. If so, we will need to report the points from all the leaves lined between mu and mu prime, and possibly, one or both wheels stored at these two lifts. Whether we should or shouldn't do that it should be checked explicitly. In our example, we will need to report the value 7 stored in the left leaf mu, but we shouldn't report data which is stored In the leaf mu prime.