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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/query-pseudocode

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

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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/query-pseudocode

Repovive

Query Pseudocode - Binary Lifting | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Query Pseudocode

(Jump by set bits)

Here is how to jump up $k$ steps from node $v$ :

function jumpUp(v, k):
    for j from log(n) down to 0:
        if k >= 2^j:
            v = up[v][j]
            k = k - 2^j
    return v

Alternatively, check bits:

function jumpUp(v, k):
    for j from 0 to log(n):
        if (k AND (1 << j)) != 0:
            v = up[v][j]
    return v

Both approaches work.