JP Journal of Algebra, Number Theory and Applications
Volume 5, Issue 2, Pages 257 - 267
(August 2005)
|
|
ORBITAL MODEL FOR A CLASS OF ALGORITHMS SOLVING THE PARTIAL SUMS PROBLEM
Adriana Toni (Spain)
|
Abstract: The design of data structures and algorithms maintaining a sequence of elements from an arbitrary commutative semigroup, subject to addition updates and prefix-sum queries, has been studied under different models. We present a new such model. It uses a couple of arrays to describe the algorithms which implement the operations. The model includes optimal solutions in terms of amortized complexity. |
Keywords and phrases: lower bounds on complexity data structures, semigroup model, partial sums. |
|
Number of Downloads: 416 | Number of Views: 1245 |
|