Graph Theory37 sections · 1633 units
Open in Course

Algorithm

(Modified Euler tour)

1.1. Compute tin[v] and tout[v] via DFS.

2.2. Build array where arr[tin[v]] = +value[v] and arr[tout[v]] = -value[v].

3.3. Use BIT or segment tree for prefix sums with point updates.

4.4. For path sum query to vv: query prefix sum from 00 to tin[v].

5.5. For value update on vv: update arr[tin[v]] and arr[tout[v]] with the delta. Each query is O(logn)O(\log n).

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