Donald Bren School of Information and Computer Sciences

Let I be the set of intervals with end points in the integers 1 ... n. Associated with each element in I is a value from a commutative semigroup S. Two operations are to be implemented: update of the value associated with an interval and query of the sum of the values associated with the intervals which include an integer.

If the values are from a commutative group (i.e., inverses exist) then there is a data structure which enables both update and query algorithms of time complexity O(log n). For the semigroup problem, the use of range trees enables both update and query algorithms of time complexity O(log^2 n).

Data structures are presented with (update,query) algorithms of complexities (log^2 n, log n), (log n, log^2 n), (log n log log n, log n log log n).