Graph Theory37 sections · 1633 units
Open in Course

Algorithm

(Euler tour plus segment tree)

1.1. Run DFS to compute tin[v] and tout[v] for all nodes.

2.2. Build array arr where arr[tin[v]] = value[v].

3.3. Build segment tree on arr supporting range sum and point update.

4.4. For subtree sum query on vv: query segment tree on range [tin[v], tout[v]].

5.5. For value update on vv: update segment tree at position tin[v]. Each query takes O(logn)O(\log n).

Space complexity is O(n)O(n) for the data structures used.