QTREE - Implementation Notes

Here is the HLD path query implementation:

function hldQuery(u, v):
    result = -infinity

    while head[u] != head[v]:
        // Move the deeper chain head up
        if depth[head[u]] < depth[head[v]]:
            swap(u, v)

        // Query from u to its chain head
        result = max(result, segTree.query(pos[head[u]], pos[u]))
        u = parent[head[u]]

    // u and v are now on the same chain
    if depth[u] > depth[v]:
        swap(u, v)

    // For edge weights, skip the LCA node
    result = max(result, segTree.query(pos[u] + 1, pos[v]))

    return result

function hldUpdate(edgeIndex, newWeight):
    // Edge i stored at node edgeNode[i]
    node = edgeNode[edgeIndex]
    segTree.update(pos[node], newWeight)

Time: $O(\log^2 n)$ per query. Space: $O(n)$.