Graph Theory37 sections · 1633 units
Open in Course

Why Subtree Tricks Fail

Paths cross subtree boundaries

Subtree queries work because every subtree forms a contiguous range in the Euler tour. You query one range in the segment tree and get your answer. Paths do not respect subtree boundaries. The path from node 55 to node 88 might go up to their lowest common ancestor at node 22, then down to node 88.

This path spans multiple subtrees. You cannot represent an arbitrary path as a single range in any tour order. The path crosses different branches of the tree. You need a different structure that handles paths explicitly.