We present a general and novel technique for solving decomposable problems on a set S whose items are sorted with respect to d > 1 total orders. We show how to dynamically maintain S in the following time bounds: O(log p) for the insertion or the deletion of a single item, where p is the number of items currently in S; O(p~((1-1)/d)) for splits and concatenates along any total order; O(p~((1-1)/d)) plus an output sensitive cost for rectangular range queries. The space required is O(p). We provide several applications of our technique ranging from two-dimensional priority queues and d-dimensional search trees to concatenable interval trees. This allows us to improve many previously known results on decomposable problems under split and concatenate operations, such as membership query, minimum-weight item, range query, and convex hulls. Our technique is suitable for efficient external memory implementation.
展开▼
