# 读 Computing the nearest common ancestor

Schieber-Vishkin算法是由Baruch Schieber 和 Uzi Vishkin 通过简化 Harel and Tarjan的算法得来的. 它的复杂度包含了两个部分, o(n)的preprocessing(预处理)阶段和o(1)的query(解答)阶段.

• a(3,4) = ((3 >> 4) | 1) << 4 = ((0) | 1) << 4 = 1 << 4 = 16 node 3的高度为4的父节点是16
• a(3,1) = ((3 >> 1) | 1) << 1 = ((1) | 1) << 1 = 1 << 1 = 2 node 3的高度为1的父节点是2
• a(3,0) = ((3 >> 0) | 1) << 0 = ((3) | 1) << 0 = 3 << 0 = 3 node3的高度为0的父节点是自己(3).

``````package graphs.lca;

import java.util.*;
import java.util.stream.Stream;

// Answering LCA queries in O(1) with O(n) preprocessing
public class LcaSchieberVishkin {
int[] parent;
int[] preOrder;
int[] I;
int[] A;
int time;

void dfs1(List<Integer>[] tree, int u, int p) {
parent[u] = p;
I[u] = preOrder[u] = time++;
for (int v : tree[u]) {
if (v == p) continue;
dfs1(tree, v, u);
if (Integer.lowestOneBit(I[u]) < Integer.lowestOneBit(I[v])) {
I[u] = I[v];
}
}
}

void dfs2(List<Integer>[] tree, int u, int p, int up) {
A[u] = up | Integer.lowestOneBit(I[u]);
for (int v : tree[u]) {
if (v == p) continue;
dfs2(tree, v, u, A[u]);
}
}

public LcaSchieberVishkin(List<Integer>[] tree, int root) {
int n = tree.length;
preOrder = new int[n];
I = new int[n];
A = new int[n];
parent = new int[n];

dfs1(tree, root, -1);
dfs2(tree, root, -1, 0);
}

int enterIntoStrip(int x, int hz) {
if (Integer.lowestOneBit(I[x]) == hz)
return x;
int hw = Integer.highestOneBit(A[x] & (hz - 1));
return parent[head[I[x] & -hw | hw]];
}

public int lca(int x, int y) {
int hb = I[x] == I[y] ? Integer.lowestOneBit(I[x]) : Integer.highestOneBit(I[x] ^ I[y]);
int hz = Integer.lowestOneBit(A[x] & A[y] & -hb);
int ex = enterIntoStrip(x, hz);
int ey = enterIntoStrip(y, hz);
return preOrder[ex] < preOrder[ey] ? ex : ey;
}

// Usage example
public static void main(String[] args) {
List<Integer>[] tree = Stream.generate(ArrayList::new).limit(5).toArray(List[]::new);