#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-advanced-tree-techniques/path-queries-ii-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-advanced-tree-techniques/path-queries-ii-implementation

Repovive

Path Queries II - Implementation - Mixed Practice: Advanced Tree Techniques | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Path Queries II - Implementation

(HLD with segment trees)

Here is the HLD path query implementation:

function pathQueriesII(n, adj, values, queries):
    // Preprocess: HLD decomposition
    runHLD(n, adj)
    buildSegmentTree(values)

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

        while head[u] != head[v]:
            if depth[head[u]] < depth[head[v]]:
                swap(u, v)
            result = max(result, segTree.query(pos[head[u]], pos[u]))
            u = parent[head[u]]

        if depth[u] > depth[v]:
            swap(u, v)
        result = max(result, segTree.query(pos[u], pos[v]))

        return result

    function update(node, newValue):
        segTree.update(pos[node], newValue)

    for query in queries:
        if query.type == "max":
            print pathMax(query.u, query.v)
        else:
            update(query.node, query.value)

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