Tight bounds for the partial-sums problem

ABSTRACT

We close the gaps between known lower and upper bounds for the online partial-sums problem in the RAM and group models of computation. If elements are chosen from an abstract group, we prove an Ω(lg n) lower bound on the number of algebraic operations that must be performed, matching a well-known upper bound. In the RAM model with b-bit memory registers, we consider the well-studied case when the elements of the array can be changed additively by δ-bit integers. We give a RAM algorithm that achieves a running time of Θ(1 + lg n / lg(b / δ)) and prove a matching lower bound in the cell-probe model. Our lower bound is for the amortized complexity, and makes minimal assumptions about the relations between n, b, and δ. The best previous lower bound was Ω(lg n = (lg lg n+lg b)), and the best previous upper bound matched only in the special case b = Θ(lg n) and δ = O(lg lg n).

REFERENCES

• 1: S. Alstrup, M. A. Bender, E. D. Demaine, M. Farach-Colton, J. I. Munro, T. Rauhe, and M. Thorup, Efficient tree layout in a multilevel memory hierarchy, arXiv:cs.DS/0211010, November 2003, http://www.arXiv.org/abs/cs.DS/0211010.
• 2: Stephen Alstrup , Thore Husfeldt , Theis Rauhe, Marked Ancestor Problems, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.534, November 08-11, 1998
• 3: Arne Andersson , Peter Bro Miltersen , Mikkel Thorup, Fusion trees can be implemented with AC0 instructions only, Theoretical Computer Science, v.215 n.1-2, p.337-344, Feb. 28, 1999 [doi>10.1016/S0304-3975(98)00172-8]
• 4: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 5: A. M. Ben-Amram and Z. Galil, A generalization of a lower bound technique due to Fredman and Saks, Algorithmica 30(1):34--66, 2001.
• 6: A. M. Ben-Amram and Z. Galil, Lower bounds for dynamic data structures on algebraic RAMs, Algorithmica 32(3):364--395, 2002.
• 7: Michael A. Bender , Gerth Stlting Brodal , Rolf Fagerberg , Dongdong Ge , Simai He , Haodong Hu , John Iacono , Alejandro López-Ortiz, The Cost of Cache-Oblivious Searching, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.271, October 11-14, 2003
• 8: W. A. Burkhard, M. L. Fredman, and D. J. Kleitman, Inherent complexity trade-offs for range query problems, Theoretical Computer Science 16:279--290, 1981.
• 9: B. Chazelle, Lower bounds for off-line range searching, Discrete & Computational Geometry 17(1):53--65, 1997.
• 10: Paul F. Dietz, Optimal Algorithms for List Indexing and Subset Rank, Proceedings of the Workshop on Algorithms and Data Structures, p.39-46, August 17-19, 1989
• 11: Peter M. Fenwick, A new data structure for cumulative frequency tables, Software—Practice & Experience, v.24 n.3, p.327-336, March 1994 [doi>10.1002/spe.4380240306]
• 12: Gudmund Skovbjerg Frandsen , Peter Bro Miltersen , Sven Skyum, Dynamic word problems, Journal of the ACM (JACM), v.44 n.2, p.257-271, March 1997 [doi>10.1145/256303.256309]
• 13: Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
• 14: Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982 [doi>10.1145/322290.322305]
• 15: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 16: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 17: Haripriyan Hampapuram , Michael L. Fredman, Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums, SIAM Journal on Computing, v.28 n.1, p.1-9, Feb. 1999 [doi>10.1137/S0097539795291598]
• 18: W. K. Hon, K. Sadakane and W. K. Sung, Succinct data structures for searchable partial sums, in Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), to appear.
• 19: Thore Husfeldt , Theis Rauhe, New Lower Bound Techniques for Dynamic Partial Sums and Related Problems, SIAM Journal on Computing, v.32 n.3, p.736-753, 2003 [doi>10.1137/S0097539701391592]
• 20: Thore Husfeldt , Theis Rauhe , Søren Skyum, Lower bounds for dynamic transitive closure, planar point location, and parantheses matching, Nordic Journal of Computing, v.3 n.4, p.323-336, Winter 1996
• 21: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 22: P. B. Miltersen, Cell probe complexity --- a survey, Advances in Data Structures Workshop, Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS'99).
• 23: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct Dynamic Data Structures, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.426-437, August 08-10, 2001
• 24: A. C. Yao, On the complexity of maintaining partial sums, SIAM Journal on Computing 14:277--288, 1985.