Subtree Queries - Implementation

Here's the solution:

function solve(tree, values, queries)
    eulerTour(root)

    // Build Fenwick tree on tour
    arr := array of size n
    for each node v
        arr[tin[v]] := values[v]
    buildFenwick(arr)

    for each query
        if query is update(u, newVal) then
            diff := newVal - values[u]
            values[u] := newVal
            fenwickUpdate(tin[u], diff)
        else // query is subtreeSum(u)
            print fenwickQuery(tout[u]) - fenwickQuery(tin[u] - 1)

Time: $O((n + q) \log n)$. Simple and efficient.