Path Queries - Walkthrough

Tree: $1 - 2 - 4$, $1 - 3$. Values: $[4, 2, 5, 1]$. After DFS: tin = [0, 1, 2, 5], tout = [7, 4, 3, 6]. BIT: arr[0] = +4, arr[7] = -4, arr[1] = +2, arr[4] = -2, arr[2] = +1, arr[3] = -1, arr[5] = +5, arr[6] = -5. Path to node $4$: prefix sum to tin[4] = 2 is $4 + 2 + 1 = 7$.

Update node $2$ to $10$: add delta $8$ at positions $1$ and $4$. Now path to $4$ sums to $15$. Breaking paths into these ranges lets you use data structures designed for array operations.