The Reverse Problem of Range Query.

We dcsign an efficient algorithm for the problem of the two-dimensional range query. In the range query problem, we specify a range of a rectangular shape in a given (n, n) array, and munt the number of points in the range. If the points have weights, we compute the sum of the weights in the range. In the problem, we give a value v and find a range whcxe sum Clluals the value. time for our algorithms is O(n310gn). We also give an algorithm with O(vn2 log2n) time. This is fast for a small v. We briefly mmpare our problem with the maximum subarray problem where we obtain a subarray that maximizes the sum. We dcsign an efficient algorithm for the problem of the two-dimensional range query. In the range query problem, we specify a range of a rectangular shape in a given (n, n) array, and munt the number of points in the range. If the points have weights, we compute the sum of the weights in the range. In the problem, we give a value v and find a range whcxe sum Clluals the value. time for our algorithms is O(n310gn). We also give an algorithm with O(vn2 log2n) time. This is fast for a small v. We briefly mmpare our problem with the maximum subarray problem where we obtain a subarray that maximizes the sum