The Reverse Problem of Range Query
Tadao Takaoka · Electronic Notes in Theoretical Computer Science · 2003
We design an efficient algorithm for the reverse 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 count the number of points in the range. If the points have weights, we compute the sum of the weights in the range. In the reverse problem, we give a value v and find a range whose sum equals the value. The time for our algorithms is O(n3 log n). We also give an algorithm with O(vn2 log2n) time. This is fast for a small v. We briefly compare our problem with the maximum subarray problem where we obtain a subarray that maximizes the sum.