DSU on Tree (Sack)
· ☕ 9 min read · ✍️ k4i
DSU on tree answers subtree queries by keeping the largest child's contribution and rebuilding only the small parts. The trick is not union-find; it is small-to-large merging hidden inside a DFS.
BIT can be used to compute the prefix sum of an array in $log(n)$ time and takes only $O(n)$ space.