草庐IT

arrays - 段树 2 * 2 ^(ceil(log(n))) - 1 的数组的内存如何？

coder 2023-06-04 原文

链接:http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ .这是引用的文字:

We start with a segment arr[0 . . . n-1]. And every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node. All levels of the constructed segment tree will be filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2n – 1. The height of the segment tree will be ceil[log(n)]. Since the tree is represented using array and relation between parent and child indexes must be maintained, size of memory allocated for segment tree will be .

这么多内存是怎么分配的(上段最后一行)？如果正确，父子索引如何存储在代码中？请给出这背后的原因。如果这是错误的，那么正确的值是多少？

最佳答案

这里发生的情况是，如果您有一个包含 n 个元素的数组，那么段树将为这 n 个条目中的每一个条目提供一个叶节点。因此，我们有 (n) 个叶节点，还有 (n-1) 个内部节点。

节点总数= n + (n-1) = 2n-1 现在，我们知道它是一棵完整的二叉树，因此高度为:ceil(Log2(n)) +1

总数节点数 = 2^0 + 2^1 + 2^2 + … + 2^ceil(Log2(n))//这是一个几何级数，其中 2^i 表示第 i 层的节点数。

求和公式 G.P. = a * (r^size - 1)/(r-1) 其中 a=2^0

总数节点数 = 1*(2^(ceil(Log2(n))+1) -1)/(2-1)

= 2* [2^ceil(Log2(n))] -1 (您需要在数组中为每个内部节点和叶节点留出空间，这些节点是这个数量的)，因此它是大小。

= O(4 * n) 大约..

你也可以这么想，让下面是段树:

    10
   /  \
  3    7
 /\    /\
1  2  3  4

如果上面是你的分段树，那么你的分段树数组将是:10,3,7,1,2,3,4 即第 0 个元素将存储第 1 项和第 2 项的总和，第 1 项将存储第 3 和第 4 和第 2 的总和将存储第 5 和第 6 项的总和!

另外，更好的解释是:如果数组大小 n 是 2 的幂，那么我们正好有 n-1 个内部节点，总和为 2n-1 个节点。但并非总是如此，我们将 n 作为 2 的幂，因此我们基本上需要大于 n 的 2 的最小幂。也就是说，

int s=1;
for(; s<n; s<<=1);

您可能会看到我的相同答案 here

关于arrays - 段树 2 * 2 ^(ceil(log(n))) - 1 的数组的内存如何？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28470692/

arraysceilstrongsegmentsectionmemorydata-structurestreesegment-tree

有关arrays - 段树 2 * 2 ^(ceil(log(n))) - 1 的数组的内存如何？的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby-on-rails - Ruby net/ldap 模块中的内存泄漏 - 2

    作为我的Rails应用程序的一部分，我编写了一个小导入程序，它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是，与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存，我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关，因为当我删除对LDAP内容的调用时，内存使用情况会很好地稳定下来。此外，不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray，它们都是LDAP库的一部分。当我运行导入时，内存使用量最终达到超过1GB的峰值。如果问题存在，我需要找到一些方法来更正我的代

  4. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  5. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  6. ruby - 在 Ruby 中实现 `call_user_func_array` - 2

    我怎样才能完成http://php.net/manual/en/function.call-user-func-array.php在ruby中？所以我可以这样做:classAppdeffoo(a,b)putsa+benddefbarargs=[1,2]App.send(:foo,args)#doesn'tworkApp.send(:foo,args[0],args[1])#doeswork,butdoesnotscaleendend 最佳答案 尝试分解数组App.send(:foo,*args)

  7. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  8. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  9. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  10. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

随机推荐