时间戳

首页 > 解决方案 > 在 O(logn) 时间内使用稀疏矩阵的 LCA

c++ - 在 O(logn) 时间内使用稀疏矩阵的 LCA

问题描述

[1]：https ://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/

for (int i=0; i<level; i++) 
    if ((diff>>i)&1) 
        v = parent[v][i];

在上面的代码中，当“(diff>>i)”为奇数时，它只跳转到第 2^ith 父级。为什么会这样？我们如何理解只有在奇数“（diff>>i）”的情况下，我们才必须跳转？

标签： c++algorithmdata-structureslowest-common-ancestor

解决方案

首先，这个答案没有解释你分享的片段。

我也真的不明白那部分代码。我不确定那里的代码是否存在错误，因为这似乎不正确。我可以在这部分分享我的功能，希望你会发现它更容易理解。我发表了一些评论以方便您的理解。

int lcaQuery(int p, int q) {
    if(depth[p] < depth[q]) {
        swap(p, q);
    }

    // uplifting p at the same level/height of q
    for(int i = level - 1; i >= 0; i--) {
        if (depth[p] - (1 << i) >= depth[q]) {
            p = parent[p][i];
        }
    }

    // if already catch q, this is the LCA
    if (p == q) return p;

    // uplifting p and q until both of their parents are same and we reach the root
    for(int i = level - 1; i >= 0; i--) {
        if (parent[p][i] != -1 and parent[p][i] != parent[q][i]) {
            p = parent[p][i];
            q = parent[q][i];
        }
    }

    // since now both p and q are in the same level, return their parent
    return parent[p][0];
}

推荐阅读