Parallelization of Dynamic Segment Trees

摘要

The dynamic segment tree data structure is used to store a set of n line segments whose end points are in the range [-∞,∞]. Given κ segments in sorted order and a segment tree storing n segments, we obtain the following results -Insertion of κ segments on to the segment tree can be completed in O(log n + log κ) time using κ processors on the EREW-PRAM; Deletion of κ segments from the segment tree can be completed in O(log n.α(i,n) + log κ) time using κ processors on the EREW-PRAM, where α(i,n) is the row inverse of the Ackermann's function for a constant i.