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

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-segment-tree

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

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

$ curl repovive.com/roadmaps/graph-theory/heavy-light-decomposition/implementation-segment-tree

Repovive

Implementation - Segment Tree - Heavy-Light Decomposition | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Implementation - Segment Tree

(Supporting range max)

Here is the segment tree implementation for HLD:

class SegmentTree:
    function build(values, n):
        size = n
        tree = array of size 4 * n

        function buildRec(node, l, r):
            if l == r:
                tree[node] = values[l]
                return
            mid = (l + r) / 2
            buildRec(2 * node, l, mid)
            buildRec(2 * node + 1, mid + 1, r)
            tree[node] = max(tree[2 * node], tree[2 * node + 1])

        buildRec(1, 0, n - 1)

    function query(node, l, r, ql, qr):
        if qr < l or r < ql:
            return -infinity
        if ql <= l and r <= qr:
            return tree[node]
        mid = (l + r) / 2
        return max(query(2*node, l, mid, ql, qr),
                   query(2*node+1, mid+1, r, ql, qr))

    function update(node, l, r, pos, val):
        if l == r:
            tree[node] = val
            return
        mid = (l + r) / 2
        if pos <= mid:
            update(2 * node, l, mid, pos, val)
        else:
            update(2 * node + 1, mid + 1, r, pos, val)
        tree[node] = max(tree[2 * node], tree[2 * node + 1])

Time: $O(\log n)$ per operation. Space: $O(n)$ .