本文共 2118 字，大约阅读时间需要 7 分钟。

介绍一种解决在线最近公共祖先（LCA）问题的高效算法——ST表，该算法建立在线性时间内的范围查询（RMy）问题之上。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int size = 500010;int n, m, s, t;int first[size], log[size], f[size][60], head[size], p[size][60];bool vis[size];struct node1 {    int path, depth;} a[size * 2];struct node2 {    int next, to;} e[size * 2];inline int read() {    int x = 0, f = 1;    char c = getchar();    while (!isdigit(c)) {        f = c == '-' ? -1 : 1;        c = getchar();    }    while (isdigit(c)) {        x = (x << 1) + (x << 3) + (c - 48);        c = getchar();    }    return x * f;}inline int write(int x) {    if (x < 0) x = -x;    if (x > 9) write(x / 10);    putchar(x % 10 + 48);}inline void add(int from, int to) {    ++t;    e[t].to = to;    e[t].next = head[from];    head[from] = t;}inline void logn() {    int i;    log[0] = -1;    for (i = 1; i <= n * 2 + 1; ++i) {        log[i] = log[i > 1] + 1;    }}inline void DFS(int x, int dep) {    ++tot;    a[tot].path = x;    a[tot].depth = dep;    first[x] = tot;    vis[x] = true;    for (int i = head[x]; i; i = e[i].next) {        if (!vis[e[i].to]) {            DFS(e[i].to, dep + 1);            a[++tot].path = x;            a[tot].depth = dep;        }    }}inline void ST() {    int i, j;    for (i = 1; i <= tot; ++i) {        f[i][0] = i;    }    for (j = 1; j <= log[tot]; ++j) {        for (i = 1; i <= tot; ++i) {            if (a[f[i][j - 1]].depth < a[f[i >> j][j - 1] != f[i >> j][j - 1] ? a[f[i >> j][j - 1]].depth : -1) {                f[i][j] = f[i >> j][j - 1];            } else {                f[i][j] = f[i][j - 1];            }        }    }}inline int rmq(int l, int r) {    int w = log[r - l + 1];    return a[f[l][w]].depth < a[f[r - (1 << w) + 1][w]] ? f[r - (1 << w) + 1][w] : f[l][w];}inline int lca(int u, int v) {    int x = first[u], y = first[v];    if (x > y) swap(x, y);    return a[rmq(x, y)].path;}
     
    
   

在上述代码中，ST表通过在树中预先记录每个节点的访问路径和深度信息，实现了LCA查询的范围查询问题。该算法通过将树的结构信息编码为二进制形式，利用并行计算提高了查询效率。

本文通过DFS遍历预处理阶段和ST表的构建阶段，实现了对大规模数据的高效处理。在实际应用中，该算法在处理RMQ问题时展现出较高的性能。

如需进一步了解具体实现细节，可以参考源文章获取完整代码和详细说明。