Graph Theory37 sections · 1633 units
Open in Course

Query Pseudocode

(Jump by set bits)

Here is how to jump up kk steps from node vv:

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.