The Complexity of Maintaining an Array and Computing Its Partial Sums
From MaRDI portal
Publication:3933742
DOI10.1145/322290.322305zbMath0477.68046OpenAlexW1985203234MaRDI QIDQ3933742
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322290.322305
data structuresperformancesalgebraic modelrandom access memorytrade-offs among complexity measureson-line complexityinformation-theoretic modelrelations among models
Related Items
Complexity models for incremental computation, On dynamic bit-probe complexity, Dynamic algorithms for the Dyck languages, Lower bounds for set intersection queries, Algorithms in the Ultra-Wide Word Model, Surreal Birthdays and Their Arithmetic, The optimal all-partial-sums algorithm in commutative semigroups and its applications for image thresholding segmentation, TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES, Lower bounds on zero-one matrices., On the time-space complexity of reachability queries for preprocessed graphs, Multidimensional segment trees can do range updates in poly-logarithmic time, Succinct Partial Sums and Fenwick Trees, Characteristic inequalities for binary trees, On the Size of Separating Systems and Families of Perfect Hash Functions, Computing prime harmonic sums, Lower bounds for matrix factorization, Partial sums on the ultra-wide word RAM, Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model, Unnamed Item, Lower bounds for matrix factorization, A Survey of Data Structures in the Bitprobe Model, Array Range Queries, Inherent complexity trade-offs for range query problems, Lower bounds for dynamic algebraic problems, Succinct dynamic cardinal trees
