data-structures - 完整的二叉树作为有效的数据结构

Question

您将得到一个大小为n（n为2的幂）的数组。数组的所有条目都初始化为零。您必须执行以下一系列在线操作序列：


Add(i,x)将x添加到条目A[i]。
报告sum(i,j) =对于任何i，从索引j到0 < i < j <= n的数组中条目的总和。


很容易看出，我们可以在O(1)时间内执行第一个操作，而在最坏的情况下，第二个操作可能会花费O(n)。您的目标是有效执行这些操作。给出一个数据结构，该结构将确保每次操作O(log n)时间

我认为解决方案是段树，但不知道我是对还是错？

Answer 1

树的解决方案：

创建一棵完整的树，其叶子是您的主菜：1,2，...，n
node.value = inserted value [if node is a leaf]
node.value = node.left.value + node.right.value [if node is not a leaf]

因此，实际上-对于每个子树，其根值是其所有节点的值之和。

更新主菜是O（logn），因为您需要一直更新总和直到根。

对于sum（i，j），我们将找到留给i的所有元素的总和，以及留给j的所有元素的总和，然后从root.value中减去它，我们将得到所需的东西。
所以：

 sum(root,i,j) = root.value - sumLeft(i,root) - sumRight(j,root)

sumLeft()和 sumRight()的计算很简单，[对于sumLeft：]只是从根开始向下到下限，每次左移时，减去右子值，这样做，对不需要的节点求和。 [说服自己为什么这么做是对的]。最后，总和只有相关节点。 [sumRight的相同原理，但我们减去左儿子）。
伪代码：

sumLeft(x,root):
  curr <- root
  sum <- root.value
  while (curr is not a leaf):
      if (x is in curr.right):
         curr <- curr.right
      else:
         sum <- sum - curr.right.value
         curr <- curr.left
  return sum
sumRight(x,root):
  curr <- root
  sum <- root.value
  while (curr is not a leaf):
      if (x is in curr.left):
         curr <- curr.left
      else:
         sum <- sum - curr.left.value
         curr <- curr.right
  return sum

因此，sum（root，i，j）要求您两次沿着树往下走，根据需要，该树仍为O（logn）。

编辑1：

这是在根上将x添加到主菜i的方式：[问题表明操作已添加到主菜而不是替换主菜，因此这是该解决方案所假定的。也可以很容易地修改为插入]。

add(root,i,x):
  root.value <- root.value + x
  if root is leaf:
      return
  else if i is in root.left:
     add(root.left,i,x)
  else:
     add(root.right,i,x)

请注意，您可以确切知道根i属于哪个子树（左或右）[如果 i < n/2在左边，否则在右边]。向自己解释如何对任何子树（不仅是根树）执行此操作。

编辑2：
具有8个元素的树的示例：

                21
      10                 11
  4        6        7        4
1  3     2  4     6   1    2   2

总结示例：

sum（4,6）应该提供 4 + 6 + 1 = 11。
sumLeft（4）应该提供 1 + 3 + 2 = 6，并提供： sumLeft(4) = 21 - 11 - 4 = 6符合预期。
sumRight（6）应该提供 2 + 2 = 4，并且它提供 sumLeft(6) = 21 - 11 - 7 =4。 [符合预期]
因此，总体而言： sum(4,6) = 21 - 6 - 4 = 11如预期。

添加示例：
add（2,4）[将4添加到第二个元素]将导致将树修改为：

                25
      14                 11
  8        6        7        4
1  7     2  4     6   1    2   2