A near optimal data structure for a type of range query problem

ABSTRACT

Let G denote the set of elements of a commutative group whose addition operations is denoted by +, let N be a positive integer, and let A(1) ,..., A(N) denote an array with values in G. We will be concerned with designing data structures for representing the array A, which facilitate efficient implementation of the following two on-line tasks: (1) Update(j,x); replace A(j) by A(j) +x. (j and x are inputs, 1≤j≤N and x&egr;G) (2) Retrieve(j); returns the value of A(1) +...+ A(j). (j is an input, 1≤j≤N) As a motivating example, let G be the group of integers with + denoting the usual addition operation. Imagine a standardized examination given to large numbers of individuals over an indefinite period of time. Assume that each examinee will attain an integer score in the interval [1,N]. If an individual gets j points, this fact is recorded by executing Update(j,1). so that A(j) represents the number of individuals to date having scored j points. In order to compute the percentile currently associated with a particular score k, we need the cumulative sum provided by executing Retrieve(k).

REFERENCES

• 1: M. L. Fredman, "The complexity of maintaining an array and computing its partial sums", to appear.
• 2: M. L. Fredman, "A lower bound on the complexity of orthogonal range queries", to appear.
• 3: Robert Endre Tarjan, Reference machines require non-linear time to maintain disjoint sets, Proceedings of the ninth annual ACM symposium on Theory of computing, p.18-29, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803392]
• 4: A. C. Yao, "Should tables be sorted?" Proc. 19th Annual Symp. on Foundations of Computer Science, 22-27, (1978).

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Management, Measurement, Theory