Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums

DOI10.1137/S0097539795291598MaRDI QIDQ4210132zbMATH OpenFDO

Authors Haripriyan Hampapuram, Michael L. Fredman

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

data structureslower boundspartial sums

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• On the Complexity of Maintaining Partial Sums
• Succinct partial sums and Fenwick trees
• Tight bounds for the partial-sums problem
• An efficient algorithm for solving the partial sum query problem
• Optimal binary trees with order constraints

Cited in

(9)

• An efficient algorithm for solving the partial sum query problem
• Algorithms in the ultra-wide word model
• Array range queries
• scientific article; zbMATH DE number 2230258 (Why is no real title available?)
• Orbital model for a class of algorithms solving the partial sums problem
• scientific article; zbMATH DE number 3881889 (Why is no real title available?)
• Lower bounds on zero-one matrices.
• Semi-group range sum revisited: query-space lower bound tightened
• Partial sums on the ultra-wide word RAM

This page was built for publication: Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210132)