Lowest Common Ancestor (LCA): Binary Lifting vs Euler Tour + ±1 RMQ Reduction

1. Paradigm A: Binary Lifting ($2^k$ Jump Pointers & Path Aggregates)

Binary Lifting stores a table $\text{up}[k][u]$ for $0 \le k \le \lfloor \log_2 N \rfloor$, where $\text{up}[0][u] = \text{parent}[u]$ and $\text{up}[k][u] = \text{up}[k-1][\text{up}[k-1][u]]$. Combined with entry/exit timestamps ($\text{tin}[u], \text{tout}[u]$), we can test whether $u$ is an ancestor of $v$ in $O(1)$ time:

$$\text{isAncestor}(u, v) \iff \text{tin}[u] \le \text{tin}[v] \;\land\; \text{tout}[v] \le \text{tout}[u]$$

To find $\text{LCA}(u, v)$ when neither is an ancestor of the other, iterate $k$ from $\lfloor \log_2 N \rfloor$ down to $0$: if $\text{up}[k][u]$ is not an ancestor of $v$, jump $u \leftarrow \text{up}[k][u]$. After the loop, $u$ is the immediate child of $\text{LCA}(u, v)$ along the path, so $\text{up}[0][u]$ is the exact LCA!

2. Production Implementation: Binary Lifting (lca, kthAncestor, dist) & $O(1)$ Euler Tour RMQ

/**
 * 1. Binary Lifting LCA + K-th Ancestor + Tree Distance
 * Build: O(N log N) | Query LCA / kthAncestor / dist: O(log N)
 */
class BinaryLiftingLCA {
  constructor(n, adj, root = 0) {
    this.n = n;
    this.LOG = Math.max(1, 32 - Math.clz32(n));
    this.up = Array.from({ length: this.LOG }, () => new Int32Array(n));
    this.depth = new Int32Array(n);
    this.tin = new Int32Array(n);
    this.tout = new Int32Array(n);
    this._build(adj, root);
  }

  _build(adj, root) {
    let timer = 0;
    // Iterative DFS to avoid call-stack overflow on deep trees (N = 2e5)
    const stack = [[root, root, 0]]; // [u, parent, childIdx]
    while (stack.length > 0) {
      const top = stack[stack.length - 1];
      const u = top[0], p = top[1], idx = top[2];
      if (idx === 0) {
        this.tin[u] = ++timer;
        this.up[0][u] = p;
        for (let k = 1; k < this.LOG; k++) {
          this.up[k][u] = this.up[k - 1][this.up[k - 1][u]];
        }
      }
      const neighbors = adj[u];
      if (idx < neighbors.length) {
        const v = neighbors[idx];
        top[2]++;
        if (v !== p) {
          this.depth[v] = this.depth[u] + 1;
          stack.push([v, u, 0]);
        }
      } else {
        this.tout[u] = ++timer;
        stack.pop();
      }
    }
  }

  isAncestor(u, v) {
    return this.tin[u] <= this.tin[v] && this.tout[v] <= this.tout[u];
  }

  kthAncestor(u, k) {
    if (k > this.depth[u]) return -1;
    for (let bit = 0; k > 0; bit++, k >>= 1) {
      if (k & 1) u = this.up[bit][u];
    }
    return u;
  }

  lca(u, v) {
    if (this.isAncestor(u, v)) return u;
    if (this.isAncestor(v, u)) return v;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if (!this.isAncestor(this.up[k][u], v)) {
        u = this.up[k][u];
      }
    }
    return this.up[0][u];
  }

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

3. Complexity Matrix