Fast and Theoretically Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps
This paper introduces MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees and develops a new batch-parallel Euler tour tree algorithm that outperforms prior batch-dynamic tree implementations supporting subtree queries, and introduces a new batch-dynamic sequence built u...