Implementing Binary Lifting Pattern

1. Applying Binary Lifting Technique

Step Description Implementation

Preprocessing

Build jump table for binary lifting

Step	Description	Implementation
Preprocessing	Build jump table for binary lifting	`const jumps = new Array(n).fill(0).map(() => new Array(20).fill(-1)); for (let i = 0; i < n; i++) { jumps[i][0] = parent[i]; } for (let j = 1; j < 20; j++) { for (let i = 0; i < n; i++) { if (jumps[i][j - 1] !== -1) { jumps[i][j] = jumps[jumps[i][j - 1]][j - 1]; } } }`
Query	Find k-th ancestor of a node	`function kthAncestor(node, k) { for (let j = 0; j < 20; j++) { if ((k >> j) & 1) { node = jumps[node][j]; if (node === -1) return -1; } } return node; }`

const jumps = new Array(n).fill(0).map(() => new Array(20).fill(-1));
for (let i = 0; i < n; i++) {
  jumps[i][0] = parent[i];
}
for (let j = 1; j < 20; j++) {
  for (let i = 0; i < n; i++) {
    if (jumps[i][j - 1] !== -1) {
      jumps[i][j] = jumps[jumps[i][j - 1]][j - 1];
    }
  }
}

Query

Find k-th ancestor of a node

function kthAncestor(node, k) {
  for (let j = 0; j < 20; j++) {
    if ((k >> j) & 1) {
      node = jumps[node][j];
      if (node === -1) return -1;
    }
  }
  return node;
}

Example: Finding k-th Ancestor

const parent = [-1, 0, 0, 1, 1, 2, 2];
const n = parent.length;
const jumps = new Array(n).fill(0).map(() => new Array(20).fill(-1));

// Preprocessing
for (let i = 0; i < n; i++) {
  jumps[i][0] = parent[i];
}
for (let j = 1; j < 20; j++) {
  for (let i = 0; i < n; i++) {
    if (jumps[i][j - 1] !== -1) {
      jumps[i][j] = jumps[jumps[i][j - 1]][j - 1];
    }
  }
}

// Query: Find 2nd ancestor of node 5
console.log(kthAncestor(5, 2)); // Output: 0

Note: Binary lifting is efficient for queries on tree structures, especially when the tree is static or updates are infrequent.

2. Building Ancestor Table

Operation	Description	Time Complexity	Space Complexity
Preprocessing	Builds a 2D table where `table[i][j]` stores the `2^j`-th ancestor of node `i`	`O(n log n)`	`O(n log n)`
Query	Find `k`-th ancestor of a node using binary lifting	`O(log k)`	-

Example: Building Ancestor Table

function buildAncestorTable(graph, root) {
  const n = graph.length;
  const log = Math.ceil(Math.log2(n));
  const table = Array(n).fill().map(() => Array(log + 1).fill(-1));

  // Initialize direct parents (2^0 ancestors)
  const visited = Array(n).fill(false);
  const queue = [root];
  visited[root] = true;

  while (queue.length) {
    const u = queue.shift();
    for (const v of graph[u]) {
      if (!visited[v]) {
        visited[v] = true;
        table[v][0] = u;
        queue.push(v);
      }
    }
  }

  // Fill the table using dynamic programming
  for (let j = 1; j <= log; j++) {
    for (let i = 0; i < n; i++) {
      if (table[i][j - 1] !== -1) {
        table[i][j] = table[table[i][j - 1]][j - 1];
      }
    }
  }

  return table;
}

Example: Query Ancestor

function getKthAncestor(node, k, table) {
  let current = node;
  for (let j = 0; j <= Math.log2(k); j++) {
    if (k & (1 << j)) {
      current = table[current][j];
      if (current === -1) break;
    }
  }
  return current;
}

Note: The ancestor table allows efficient querying of any k-th ancestor in O(log k) time after O(n log n) preprocessing.

3. Finding Kth Ancestor

Property	Description	Usage
parent	Array storing the direct parent of each node	`parent[u] = v` means `v` is the parent of `u`
up	2D array for binary lifting; `up[u][i]` is the `2^i`-th ancestor of node `u`	`up[u][i] = parent[up[u][i-1]]`
depth	Depth of each node from root	`depth[u] = depth[parent[u]] + 1`

Example: Binary Lifting Setup

const MAX_LOG = 20;
const up = Array(100000).fill().map(() => Array(MAX_LOG).fill(-1));
const parent = Array(100000).fill(-1);
const depth = Array(100000).fill(0);

function preprocess(node, par, d) {
    parent[node] = par;
    depth[node] = d;
    up[node][0] = par;

    for (let i = 1; i < MAX_LOG; i++) {
        if (up[node][i - 1] !== -1) {
            up[node][i] = up[up[node][i - 1]][i - 1];
        } else {
            up[node][i] = -1;
        }
    }

    // Process children recursively
}

Example: Find Kth Ancestor

function kthAncestor(node, k) {
    for (let i = 0; i < MAX_LOG; i++) {
        if ((k & (1 << i)) !== 0) {
            if (node === -1) return -1;
            node = up[node][i];
        }
    }
    return node;
}

Note: The binary lifting technique allows for O(log n) query time after O(n log n) preprocessing.

4. Implementing Lowest Common Ancestor

Operation	Description	Time Complexity	Space Complexity
LCA Query	Finds the lowest common ancestor of two nodes in a tree	`O(log n)`	`O(n log n)`
Preprocessing	Builds binary lifting table for efficient queries	`O(n log n)`	`O(n log n)`

Example: LCA Implementation with Binary Lifting

class LCA {
  constructor(tree, root = 0) {
    this.n = tree.length;
    this.depth = new Array(this.n).fill(0);
    this.parent = new Array(this.n).fill(-1);
    this.up = Array(this.n).fill().map(() => new Array(20).fill(-1));
    this.dfs(tree, root, -1, 0);
    this.build();
  }

  dfs(tree, u, p, d) {
    this.depth[u] = d;
    this.parent[u] = p;
    for (let v of tree[u]) {
      if (v !== p) this.dfs(tree, v, u, d + 1);
    }
  }

  build() {
    for (let j = 0; j < 20; j++) {
      for (let i = 0; i < this.n; i++) {
        if (j === 0) {
          this.up[i][j] = this.parent[i];
        } else {
          this.up[i][j] = this.up[this.up[i][j - 1]][j - 1];
        }
      }
    }
  }

  query(u, v) {
    if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
    for (let i = 19; i >= 0; i--) {
      if (this.depth[u] - this.depth[v] >= (1 << i)) {
        u = this.up[u][i];
      }
    }
    if (u === v) return u;
    for (let i = 19; i >= 0; i--) {
      if (this.up[u][i] !== this.up[v][i]) {
        u = this.up[u][i];
        v = this.up[v][i];
      }
    }
    return this.parent[u];
  }
}

// Example usage:
const tree = [[1, 2], [3, 4], [5, 6]];
const lca = new LCA(tree);
console.log(lca.query(3, 5)); // Output: 0

Note: Binary lifting is particularly useful for answering queries about paths in trees, especially when the tree structure remains static.

5. Preprocessing Tree Structure

Step	Description	Implementation
Build adjacency list	Represent tree as an undirected graph using adjacency lists	`const adj = Array(n).fill().map(() => []);<br>for (let i = 0; i < n - 1; i++) {<br> const [u, v] = edges[i];<br> adj[u].push(v);<br> adj[v].push(u);<br>}`
Root the tree	Choose a root node (typically 0) and perform DFS to assign parent and depth	`const parent = Array(n).fill(-1);<br>const depth = Array(n).fill(0);<br><br>function dfs(node, par, d) {<br> parent[node] = par;<br> depth[node] = d;<br> for (let child of adj[node]) {<br> if (child !== par) dfs(child, node, d + 1);<br> }<br>}`
Initialize binary lifting table	Precompute ancestors at powers of 2 for each node	`const LOG = Math.ceil(Math.log2(n));<br>const up = Array(n).fill().map(() => Array(LOG).fill(-1));<br><br>function preprocess() {<br> for (let i = 0; i < n; i++) up[i][0] = parent[i];<br> for (let j = 1; j < LOG; j++) {<br> for (let i = 0; i < n; i++) {<br> if (up[i][j - 1] !== -1)<br> up[i][j] = up[up[i][j - 1]][j - 1];<br> }<br> }<br>}`

Example: Tree with 5 nodes

const edges = [[0, 1], [0, 2], [1, 3], [1, 4]];<br>const n = 5;

Note: The binary lifting table up[i][j] stores the 2^j-th ancestor of node i.

6. Calculating Level Depths

Level	Depth	Description
0	`0`	Root level, no parent
1	`1`	Immediate children of root
2	`2`	Children of level 1 nodes
3	`3`	Children of level 2 nodes
n	`n`	Children of level n-1 nodes

Example: Depth Calculation for Binary Tree

function calculateDepth(node) {
  if (!node) return 0;
  return 1 + Math.max(calculateDepth(node.left), calculateDepth(node.right));
}

7. Solving Range Queries on Paths

Binary lifting is particularly useful for answering range queries on paths in trees, such as finding the lca (Lowest Common Ancestor) or computing range sums/minimums on paths between nodes.

Example: Finding LCA using Binary Lifting

class BinaryLifting {
    constructor(n, edges) {
        this.n = n;
        this.adj = Array(n).fill().map(() => []);
        for (let [u, v] of edges) {
            this.adj[u].push(v);
            this.adj[v].push(u);
        }
        this.depth = Array(n).fill(0);
        this.parent = Array(n).fill(-1);
        this.up = Array(n).fill().map(() => Array(20).fill(-1));
        this.dfs(0, -1, 0);
        this.build();
    }

    dfs(u, p, d) {
        this.depth[u] = d;
        this.parent[u] = p;
        for (let v of this.adj[u]) {
            if (v !== p) {
                this.dfs(v, u, d + 1);
            }
        }
    }

    build() {
        for (let j = 0; j < 20; j++) {
            for (let i = 0; i < this.n; i++) {
                if (j === 0) {
                    this.up[i][j] = this.parent[i];
                } else {
                    this.up[i][j] = this.up[this.up[i][j - 1]][j - 1];
                }
            }
        }
    }

    getLCA(u, v) {
        if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
        let k = this.depth[u] - this.depth[v];
        for (let j = 0; j < 20; j++) {
            if ((k >> j) & 1) u = this.up[u][j];
        }
        if (u === v) return u;
        for (let j = 19; j >= 0; j--) {
            if (this.up[u][j] !== this.up[v][j]) {
                u = this.up[u][j];
                v = this.up[v][j];
            }
        }
        return this.up[u][0];
    }

    getDistance(u, v) {
        const lca = this.getLCA(u, v);
        return this.depth[u] + this.depth[v] - 2 * this.depth[lca];
    }
}

// Example usage:
const edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]];
const bl = new BinaryLifting(7, edges);
console.log(bl.getLCA(3, 4)); // Output: 1
console.log(bl.getDistance(3, 6)); // Output: 4

Operation	Description	Time Complexity	Space Complexity
getLCA(u, v)	Finds the lowest common ancestor of nodes u and v	`O(log n)`	`O(n log n)`
getDistance(u, v)	Computes the distance between nodes u and v	`O(log n)`	`O(n log n)`

Note: The binary lifting table up[i][j] stores the 2^j-th ancestor of node i. This allows for efficient path queries by jumping up in powers of two.

8. Finding Distance Between Nodes

Operation	Description	Time Complexity	Space Complexity
Distance(u, v)	Calculates the shortest path distance between nodes u and v using binary lifting	`O(log n)`	`O(n log n)`

Example: Calculating Distance Between Nodes

function findDistance(u, v, parent, depth, up) {
    const lca = findLCA(u, v, up, depth);
    return depth[u] + depth[v] - 2 * depth[lca];
}

// Example usage:
const u = 5, v = 9;
const distance = findDistance(u, v, parent, depth, up);
console.log("Distance between nodes " + u + " and " + v + ": " + distance);

Note: The distance is calculated using the lowest common ancestor (LCA) and the depths of nodes in the tree.

9. Optimizing Space Complexity

Approach	Description	Space Complexity	Notes
Sparse Table	Precompute ancestors at powers of 2 for each node	`O(n log n)`	Best for static trees with frequent queries
Binary Lifting with Compression	Store only necessary levels, compress sparse entries	`O(n)`	Reduces memory overhead for sparse trees
Lazy Evaluation	Compute ancestors only when needed	`O(n)`	Good for trees with infrequent queries

Example: Sparse Table Construction

const n = 1000;
const logN = Math.ceil(Math.log2(n));
const up = Array(n).fill().map(() => Array(logN + 1).fill(-1));

// Precompute ancestors at powers of 2
for (let i = 0; i < n; i++) {
  up[i][0] = parent[i]; // direct parent
}

for (let j = 1; j <= logN; j++) {
  for (let i = 0; i < n; i++) {
    if (up[i][j - 1] !== -1) {
      up[i][j] = up[up[i][j - 1]][j - 1];
    }
  }
}

Note: The space complexity can be reduced by storing only the necessary levels or using lazy evaluation techniques to avoid precomputing all ancestors.

10. Implementing Path Queries

Operation	Description	Time Complexity	Space Complexity
queryPath(u, v)	Find the path between nodes u and v in a tree using binary lifting	O(log n)	O(n log n)
queryLCA(u, v)	Find the Lowest Common Ancestor (LCA) of nodes u and v	O(log n)	O(n log n)
queryDistance(u, v)	Calculate the distance between nodes u and v	O(log n)	O(n log n)

Example: Path Query Implementation

class BinaryLifting {
  constructor(n, edges) {
    this.n = n;
    this.tree = new Array(n).fill().map(() => []);
    this.parent = new Array(n).fill(-1);
    this.depth = new Array(n).fill(0);
    this.up = new Array(n).fill().map(() => new Array(20).fill(-1));
    
    for (let [u, v] of edges) {
      this.tree[u].push(v);
      this.tree[v].push(u);
    }
    
    this.dfs(0, -1);
    this.build();
  }

  dfs(u, p) {
    this.parent[u] = p;
    this.depth[u] = p === -1 ? 0 : this.depth[p] + 1;
    for (let v of this.tree[u]) {
      if (v !== p) {
        this.dfs(v, u);
      }
    }
  }

  build() {
    for (let i = 0; i < this.n; i++) {
      this.up[i][0] = this.parent[i];
    }
    
    for (let j = 1; (1 << j) < this.n; j++) {
      for (let i = 0; i < this.n; i++) {
        if (this.up[i][j - 1] !== -1) {
          this.up[i][j] = this.up[this.up[i][j - 1]][j - 1];
        }
      }
    }
  }

  queryLCA(u, v) {
    if (this.depth[u] < this.depth[v]) [u, v] = [v, u];
    
    let k = this.depth[u] - this.depth[v];
    for (let j = 0; (1 << j) <= k; j++) {
      if (k & (1 << j)) u = this.up[u][j];
    }

    if (u === v) return u;

    for (let j = 19; j >= 0; j--) {
      if (this.up[u][j] !== this.up[v][j]) {
        u = this.up[u][j];
        v = this.up[v][j];
      }
    }

    return this.up[u][0];
  }

  queryDistance(u, v) {
    const lca = this.queryLCA(u, v);
    return this.depth[u] + this.depth[v] - 2 * this.depth[lca];
  }
}

Note: The binary lifting technique uses precomputed ancestors at powers of two to efficiently answer queries about paths and distances in trees.