草庐IT

c++ - 最低公共(public)祖先优化

coder 2024-02-21 原文

我有一个包含元素 [0 到 N - 1] 的基本数组，其中每个元素都是一个结构，其索引始终 指向数组中较早的位置.

有一次，作为一个更大算法的一部分，我想在节点 X 和之后的任何节点之间找到一个特定的 C 最低共同祖先。

int LCA(a, b) {
    while (a != b) {
        if (a > b) {
            a = nodes[a].parent;
        } else {
            b = nodes[b].parent;
        }
    }
    return a;
}

for (y = x + 1; y < n; ++y) {
    if (LCA(x, y) == c) {
        //other code
    }
}

上面的代码真的是伪代码。通过在使用时生成查找表，我设法稍微提高了 LCA() 的性能。像这样:

int LCA(a, b) {
    if (lookup[a, b]) {
        return lookup[a, b];
    }
    oa = a; ob = b;
    while (a != b) {
        if (a > b) {
            a = nodes[a].parent;
        } else {
            b = nodes[b].parent;
        }
    }
    lookup[oa, ob] = a;
    lookup[ob, oa] = a;
    return a;
}

我知道我可能有一种方法可以制作某种专门的 LCA() 函数，也就是说，以某种方式替换上面的所有代码以使其专门化，从而使其速度相当快。但是我没有想到任何有趣的事情。

我试图通过查看 LCA(c, y) == LCA 是否可以简单地在 C 和 Y 之间进行 LCA 检查(x, y)，但这当然不准确。

回顾一下:X 总是小于 Y。 C 总是小于 X(因此 Y)。 parent 的指数总是低于他们的 child (因此是有序的)。

节点知道它们的深度有什么帮助吗？

这段代码占整个算法CPU时间的80%，总共耗时约4分钟。对此的解决方案很容易改进整个算法。谢谢!

最佳答案

x 和 y 的 LCA 将是 x 和 y 出现之间高度最小的节点在 euler tour 中出现 y (*) 你的树。要在 O(1) 时间内找到它，您需要解决 RMQ problem使用 this method .

(*):您的导览需要稍作修改才能正常工作。每次返回数组时(从对子项的递归调用返回)，您也必须向数组附加一个值。对于 wiki 树，它看起来像这样:

1 2 3 4 5 6 7 8 9 10 11
1 2 6 2 4 2 1 3 1 5  1

请注意，叶子出现两次是没有意义的(尽管它不会影响正确性)。

因此，例如，RMQ(2, 5) 将是这些节点中具有最小高度的节点:

2 3 4 5 6 7 8 9 10
2 6 2 4 2 1 3 1 5

这是节点 1。

这不是您可以采取的唯一有效间隔。取最后一次出现的 2 也是有效的:

6 7 8 9 10
2 1 3 1 5

这也将返回 1 作为 LCA。

通过这种方式，您可以在恒定时间内回答 LCA 查询，而花费在预处理上的时间是线性的。

关于c++ - 最低公共(public)祖先优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19015012/

amppubliccodesectionemc++calgorithmtree

有关c++ - 最低公共(public)祖先优化的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - Sinatra set cache_control to static files in public folder编译错误 - 2

    我不知道为什么，但是当我设置这个设置时它无法编译设置:static_cache_control，[:public，:max_age=>300]这是我得到的syntaxerror,unexpectedtASSOC,expecting']'(SyntaxError)set:static_cache_control,[:public,:max_age=>300]^我只想将“过期”header设置为css、javaascript和图像文件。谢谢。 最佳答案 我猜您使用的是Ruby1.8.7。Sinatra文档中显示的语法似乎是在Ruby1.

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2

    假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案 您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby - "public/protected/private"方法是如何实现的，我该如何模拟它？ - 2

    在ruby中，你可以这样做:classThingpublicdeff1puts"f1"endprivatedeff2puts"f2"endpublicdeff3puts"f3"endprivatedeff4puts"f4"endend现在f1和f3是公共(public)的，f2和f4是私有(private)的。内部发生了什么，允许您调用一个类方法，然后更改方法定义？我怎样才能实现相同的功能(表面上是创建我自己的java之类的注释)例如...classThingfundeff1puts"hey"endnotfundeff2puts"hey"endendfun和notfun将更改以下函数定

  7. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  8. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  9. ruby - private、protected 和 public 的范围 - 2

    在Ruby类定义中，private关键字在以下场景中的作用域是什么:classFoodefbar_publicputs"public"endprivatedefbar_privateputs"private"enddefbar_public_2puts"anotherpublic"endendprivate是否只作用于bar_private？还是在bar_public_2上？ 最佳答案 在您的例子中，bar_private和bar_public_2都是私有(private)的。那是因为这两种方法都在private关键字的“范围内”。

  10. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

随机推荐