Path Queries - Analysis

Why not simpler approaches? Sqrt decomposition: Paths can have $O(n)$ nodes.

Even with blocking, queries would be $O(\sqrt{n} \cdot$ path length$)$, which is too slow.

Euler tour + segment tree: Works for subtree queries, but path queries need ancestor information that Euler tours don't preserve well.

HLD: Converts any path into $O(\log n)$ contiguous segments.

Each segment maps to a range in a single segment tree. Point updates are also $O(\log n)$. Time: $O((n + q) \log^2 n)$. Space: $O(n)$.