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

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-path-query

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

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

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-path-query

Repovive

Implementation - Path Query - Heavy-Light Decomposition | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Implementation - Path Query

(Combining chain segments)

To query the maximum on path from $u$ to $v$ :

function path_query(u, v)
    res := -infinity
    while chain[u] != chain[v]
        if depth[head[u]] < depth[head[v]] then
            swap(u, v)
            res := max(res, seg_query(pos[head[u]], pos[u]))
            u := parent[head[u]]
            if depth[u] > depth[v] then
                swap(u, v)
                res := max(res, seg_query(pos[u], pos[v]))
                return res

This walks $O(\log n)$ chains, querying each one and tracking the maximum.

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