2015 | OriginalPaper | Buchkapitel
Simple Parallel Algorithms for Dynamic Range Products
Erschienen in:
Algorithms, Probability, Networks, and Games
Abstract
We consider here the problem of answering range product queries on an n-node unrooted tree labelled with elements of a semigroup provided with an associative operator only. We present simple parallel dynamic algorithms for one of the weakest models of parallel computation (EREW PRAM). Our main result is an algorithm which answers a query in \(O(\alpha (n))\) time using a single processor after \(O(\log n)\)-time and O(n)-work preprocessing, where \(\alpha (n)\) is the inverse of Ackermann’s function. The data structures set up during preprocessing are updated in \(O(\log n)\) time and \(O(n^\beta )\) work, for any (arbitrarily small) constant \(0<\beta <1\), after a dynamic change in the label of a tree node.
