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

$ curl repovive.com/roadmaps/data-structures/advanced-trees/hld-path-query-code

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

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

$ curl repovive.com/roadmaps/data-structures/advanced-trees/hld-path-query-code

Repovive

HLD Path Query - Code - Advanced Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

HLD Path Query - Code

The implementation

Here's path maximum query:

function pathMax(u, v)
 result := -infinity
 while chainHead[u] ≠ chainHead[v]
 if depth[chainHead[u]] < depth[chainHead[v]] then
 swap(u, v)
 // Query from u to its chain head
 result := max(result, segmentTreeQuery(pos[chainHead[u]], pos[u]))
 u := parent[chainHead[u]]

 // Now u and v are in the same chain
 if depth[u] > depth[v] then
 swap(u, v)
 result := max(result, segmentTreeQuery(pos[u], pos[v]))
 return result

Time: $O(\log^2 n)$ . The outer while loop runs $O(\log n)$ times, each iteration does an $O(\log n)$ segment tree query.