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)

Full work available at URL https://doi.org/10.1137/S0097539795291598

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)

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

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)