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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/company-queries-i-implementation

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

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

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/company-queries-i-implementation

Repovive

Company Queries I - Implementation - Binary Lifting | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Company Queries I - Implementation

Binary lifting code

Build $up$ table:

for i = 2 to n:
 up[i][0] = parent[i]
up[1][0] = 1 // root's parent is itself

for j = 1 to log(n):
 for i = 1 to n:
 up[i][j] = up[up[i][j-1]][j-1]

Answer query $(v, k)$ :

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

This runs in $O(n \log n)$ time and uses $O(n \log n)$ space.