Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Subtree to Range

(The key observation)

If you flatten the tree with Euler tour, each subtree becomes a range [tin[v], tout[v]] in the flattened array. Subtree sum query for node vv = range sum query on [tin[v], tout[v]]. Update node vv = point update at position tin[v].

This is exactly what segment trees handle: point updates and range queries in O(logn)O(\log n). The range representation means you can use efficient range query structures to answer subtree questions in logarithmic time.