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 k segments in sorted order and a segment tree storing n segments, we obtain the following results - Insertion of k segments on to the segment tree can be completed in O(logn + log k) time using k processors on the EREW-PRAM; Deletion of k segments from the segment tree can be completed in O(log n.α(i, n) + log k) time using k processors on the EREW-PRAM, where α(i,n) is the row inverse of the Ackermann's function for a constant i.