支持Add和Partial

支持Add和Partial-Sum的数据结构(Data structure supporting Add and Partial-Sum)

设A [1..n]是实数的数组。 设计算法以执行以下操作的任何顺序：

Add(i,y) -- Add the value y to the ith number. Partial-sum(i) -- Return the sum of the first i numbers, i.e.

没有插入或删除; 唯一的变化是数字的值。 每个操作都应该采取O（logn）步骤。 您可以使用另一个大小为n的数组作为工作空间。

如何设计上述算法的数据结构？

Let A[1..n] be an array of real numbers. Design an algorithm to perform any sequence of the following operations:

Add(i,y) -- Add the value y to the ith number. Partial-sum(i) -- Return the sum of the first i numbers, i.e.

There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take O(logn) steps. You may use one additional array of size n as a work space.

How to design a data structure for above algorithm?

最满意答案

用n个叶子构造一个平衡的二叉树; 以原始顺序粘贴树底部的元素。

用“子树叶子总和”增加树中的每个节点; 一棵树有＃leaves-1个节点，所以这需要O（n）的设置时间（我们有）。

查询部分和是这样的：向查询（叶）节点下降树，但每当你向右下降时，在左边添加子树和加上你刚刚访问的元素，因为这些元素在总和中。

修改值如下所示：查找查询（左）节点。 计算您添加的差异。 前往树的根部; 当您前往根目录时，通过添加差异来更新您访问的每个节点（您可能需要访问相邻节点，具体取决于您是否存储“子树叶子总和”或“左子树加上我自己”或一些变种）; 主要思想是适当地更新所有需要更新的扩充分支数据，并且数据将位于根路径上或与其相邻。

这两个操作占用O（log（n））时间（即树的高度），并且在每个节点上执行O（1）工作。

您可以使用任何搜索树（例如，自平衡二进制搜索树可能允许插入，其他搜索树可以更快访问）但我没有想到通过。

Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.

Augment each node in the tree with "sum of leaves of subtree"; a tree has #leaves-1 nodes so this takes O(n) setup time (which we have).

Querying a partial-sum goes like this: Descend the tree towards the query (leaf) node, but whenever you descend right, add the subtree-sum on the left plus the element you just visited, since those elements are in the sum.

Modifying a value goes like this: Find the query (left) node. Calculate the difference you added. Travel to the root of the tree; as you travel to the root, update each node you visit by adding in the difference (you may need to visit adjacent nodes, depending if you're storing "sum of leaves of subtree" or "sum of left-subtree plus myself" or some variant); the main idea is that you appropriately update all the augmented branch data that needs updating, and that data will be on the root path or adjacent to it.

The two operations take O(log(n)) time (that's the height of a tree), and you do O(1) work at each node.

You can probably use any search tree (e.g. a self-balancing binary search tree might allow for insertions, others for quicker access) but I haven't thought that one through.

支持Add和Partial-Sum的数据结构(Data structure supporting Add and Partial-Sum)

设A [1..n]是实数的数组。 设计算法以执行以下操作的任何顺序：

Add(i,y) -- Add the value y to the ith number. Partial-sum(i) -- Return the sum of the first i numbers, i.e.

没有插入或删除; 唯一的变化是数字的值。 每个操作都应该采取O（logn）步骤。 您可以使用另一个大小为n的数组作为工作空间。

如何设计上述算法的数据结构？

Let A[1..n] be an array of real numbers. Design an algorithm to perform any sequence of the following operations:

Add(i,y) -- Add the value y to the ith number. Partial-sum(i) -- Return the sum of the first i numbers, i.e.

There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take O(logn) steps. You may use one additional array of size n as a work space.

How to design a data structure for above algorithm?

最满意答案

用n个叶子构造一个平衡的二叉树; 以原始顺序粘贴树底部的元素。

用“子树叶子总和”增加树中的每个节点; 一棵树有＃leaves-1个节点，所以这需要O（n）的设置时间（我们有）。

查询部分和是这样的：向查询（叶）节点下降树，但每当你向右下降时，在左边添加子树和加上你刚刚访问的元素，因为这些元素在总和中。

修改值如下所示：查找查询（左）节点。 计算您添加的差异。 前往树的根部; 当您前往根目录时，通过添加差异来更新您访问的每个节点（您可能需要访问相邻节点，具体取决于您是否存储“子树叶子总和”或“左子树加上我自己”或一些变种）; 主要思想是适当地更新所有需要更新的扩充分支数据，并且数据将位于根路径上或与其相邻。

这两个操作占用O（log（n））时间（即树的高度），并且在每个节点上执行O（1）工作。

您可以使用任何搜索树（例如，自平衡二进制搜索树可能允许插入，其他搜索树可以更快访问）但我没有想到通过。

Construct a balanced binary tree with n leaves; stick the elements along the bottom of the tree in their original order.

Augment each node in the tree with "sum of leaves of subtree"; a tree has #leaves-1 nodes so this takes O(n) setup time (which we have).

Querying a partial-sum goes like this: Descend the tree towards the query (leaf) node, but whenever you descend right, add the subtree-sum on the left plus the element you just visited, since those elements are in the sum.

Modifying a value goes like this: Find the query (left) node. Calculate the difference you added. Travel to the root of the tree; as you travel to the root, update each node you visit by adding in the difference (you may need to visit adjacent nodes, depending if you're storing "sum of leaves of subtree" or "sum of left-subtree plus myself" or some variant); the main idea is that you appropriately update all the augmented branch data that needs updating, and that data will be on the root path or adjacent to it.

The two operations take O(log(n)) time (that's the height of a tree), and you do O(1) work at each node.

You can probably use any search tree (e.g. a self-balancing binary search tree might allow for insertions, others for quicker access) but I haven't thought that one through.