algorithm - 序列的部分乘积的节省空间的数据结构？

Question

我需要建议一个具有O(n)内存复杂度的数据结构来执行以下操作：
Init()–初始化空数据结构。
Insert (I,x)-在i位插入数字x。i位之前和之后的数字将比i位高一个索引。复杂性：O(logn)。
Get(i)–返回i元素复杂性：O(logn)。
multiplyAllBut(down,up)-返回乘法数，但不返回出现在上下位置之间的数字。复杂性：O(logn)。
我考虑过avl树，但我在更改索引时遇到了问题。此外，跳过列表，但不是在安魂曲的复杂性。
谢谢。：）

Answer 1

除了最后一个操作（将所有内容乘以一个值），您可以使用order statistic tree来实现这一点，这是一个扩展的bst，其中每个节点将元素的数量存储在左侧和右侧。我相信，从这个数据结构开始，添加更多的信息，您可以让所有四个操作高效地工作。
基本思想如下：扩展树中的每个节点，将所有数字的乘积存储在左子树中，将所有数字的乘积存储在右子树中。我们称之为leftProd和rightProd。这些值可以在时间O（1）中从节点的左、右子树中的值和节点本身的值来计算，因此用该额外信息增强树不会改变实现的渐近时间复杂度。另外，存储两个值：minIndex和maxIndex，子树中的最小和最大索引是在给定节点上生根的。这两个值可以从左子树和右子树中的值有效地计算出来，因此不需要增加额外的扩展。
现在，假设要查找范围[低，高]中的值的乘积为此，递归搜索树，如下所示：
如果[低，高]纯粹位于当前节点索引的左侧，则递归计算左侧子树中的值。
如果[low，high]纯粹位于当前节点索引的右侧，则递归计算右侧子树中的值。
如果[低，高]正好匹配范围[minIndex, maxIndex]，则返回节点的vaule，leftProd和rightProd的乘积。
否则，在左子树中对[low，index-1]进行递归调用，在右子树中对[index+1，high]进行递归调用，并返回这两个数字与节点自身值的乘积。
我们需要证明为什么这会有效。这个想法的关键是以下几点。案例1和案例2只进行一次递归调用。案例3不进行递归调用案例4将进行两次递归调用。每个案例都有O（1）个案例。如果不是在案例4中完成的分支，递归将从树的顶部向下遍历，每个级别执行O（1）个工作，因此完成的总工作是O（log n）。
然而，我要说的是，案例4实际上并没有你想象的那么多分支想象一下在递归中第一次发生case 4。当它这样做时，它将进行两次递归调用，一次向左，一次向右注意，这些递归调用是针对非常特定的子范围的：左子树上的调用要求从某个索引到左子树中的最后一个索引的范围，右子树上的调用要求从右子树中的第一个索引到某个索引的范围。换言之，递归调用是在子范围上进行的，这些子范围“刷新”到它们重新进入的子树的一侧。
现在，想想从那一点开始我们遇到案例4的任何时候。每当我们这样做时，我们知道递归将下降到的两个范围中的一个将包含一个完整子树的范围这将立即导致我们遇到情况3，因此递归调用实际上不是真正的递归调用。这意味着Case 4能够“真正”分支的次数最多只有一次从这一点开始，递归实际上只沿着树中的一条路径继续。
总的来说，这意味着我们可以将完成的总工作（至少是渐近的）限制为从树的顶部到底部行走两次所需的工作，每个节点执行o（1）个工作。根据需要，计算出总工时为o（log n）。
我们需要多少空间？这种扩展每个节点仅使用o（1）个空间，因此所需的总空间为o（n）。
希望这有帮助！