Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems

AbstractFredman has shown that Ω(logk N) lower bounds the complexity for doing aggregate orthogonal range queries on a set of N records in a dynamic environment, where the computing machine can use only addition for calculating aggregates. We introduce a natural k-dimensional analog to the Karlsson-Munro-Robertson (1985, in “The 12th ICALP Symposium,” pp. 318–327) contiguous segment assumption. This assumption is shown to be sufficient to extend Fredman's formalism so that subtraction as well as addition may be included in the Ω(logk N) lower bound. Since subtraction operations are known to speed up orthogonal range queries for static data structures with polylog memory redunduncy, it is significant that subtraction is not also helpful in a dynamic environment. The techniques introduced in Section 2 are stated in very general terms because they should have applications to other types of problems, besides those we consider