Parallel Batch Queries on Dynamic Trees: Algorithms and Experiments

Dynamic tree data structures maintain a forest while supporting insertion and deletion of edges and a broad set of queries in O(log n) time per operation. Such data structures are at the core of many modern algorithms. Recent work has extended dynamic trees to support batches of requests in parallel, and these parallel batch-dynamic trees are now used in several parallel algorithms.