Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums

DOI10.1137/S0097539795291598zbMATH Open0914.68041MaRDI QIDQ4210132FDOQ4210132

Authors: Haripriyan Hampapuram, Michael L. Fredman 

Publication date: 21 September 1998

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

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

zbMATH Keywords

data structureslower boundspartial sums

Mathematics Subject Classification ID

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

Cited In (9)

• Title not available (Why is that?)
• 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
• Algorithms in the Ultra-Wide Word Model
• Lower bounds on zero-one matrices.
• Partial sums on the ultra-wide word RAM
• Array Range Queries
• Title not available (Why is that?)

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)