Euler Tour Trees (ETT) are another dynamic tree structure: - Store Euler tour of tree in a balanced BST - Link/cut by splicing tours - Subtree queries are range queries on tour Comparison: | | Link-Cut | ETT | |---|---|---| | Path query | | | | Subtree query | Complex | | | Implementation | Hard | Medium | ETT is better for subtree operations.
Link-Cut is better for path operations. Choose based on what queries you need.