To query a path from to :
Find LCA of and
Query the path from to LCA
Query the path from to LCA For each path segment, climb chain by chain: - While and are in different chains, query the chain containing the deeper node, then jump to the chain head's parent - When in the same chain, query the range between them Each chain query is a segment tree range query. At most chains are visited, so total time is .