我需要建议一个内存复杂度为O(n)的数据结构，它执行以下操作:
-
Init()-初始化一个空数据结构。 -
Insert (I,x)-在第I位插入数字x，前I位和后I位的数字将高一个索引。复杂度:O(logn). -
Get(i)-返回第i元素。复杂度:O(logn). -
multiplyAllBut(down,up)-返回没有出现在上下位置之间的数字的乘法数。复杂度:O(logn).
我想过AVL树，但我有改变索引的问题。而且，跳过列表，但它没有在所需的复杂性。
谢谢。:)
除了最后一个操作(将所有内容乘以一个值)之外，您可以使用顺序统计树来实现它，这是一个扩充的BST，其中每个节点存储向左和向右的元素数量。我相信，从这个数据结构开始，再加入一些信息，你可以让这四个操作有效地工作。
基本思想如下:增加树中的每个节点来存储左子树中所有数字的乘积和右子树中存储的所有数字的乘积。我们称它们为leftProd和rightProd。这些值可以在O(1)时间内从节点的左右子树中的值和节点本身的值计算出来，因此用这些额外的信息增加树并不会改变实现的渐近时间复杂度。此外，存储另外两个值:minIndex和maxIndex，它们是在给定节点上根的子树中的最小和最大索引。这两个值可以从左子树和右子树的值有效地计算出来，所以不需要增加额外的增量。
现在，假设您想要查找[low, high]范围内值的乘积。为此，按如下方式递归搜索树:
- 如果[low, high]仅在当前节点索引的左侧，则递归计算左子树中的值。
- 如果[low, high]仅在当前节点索引的右侧，则递归计算右子树中的值。
- 如果[low, high]与范围
[minIndex, maxIndex]完全匹配，则返回该节点的值、leftProd和rightProd的乘积。 - 否则，在左子树中递归调用[low, index - 1]，在右子树中递归调用[index + 1, high]，并返回这两个数字的乘积和节点自身的值。
我们需要证明为什么这将有效地工作。这个想法的关键如下。情形1和情形2只进行一次递归调用。情形3不进行递归调用。情形4将进行两次递归调用。每种情况各做0(1)个功。如果没有情况4中的分支，递归就会从树的顶部向下走，每层做O(1)个功，所以完成的总功是O(log n)。
然而，我要声明的是，案例4实际上并不像你想象的那么多分支。想象在递归中第一次发生情形4。当它这样做时，它将进行两次递归调用，一次向左，一次向右。注意，这些递归调用是针对非常具体的子范围的:对左子树的调用请求从左子树的某个索引到最后一个索引的范围，对右子树的调用请求从右子树的第一个索引到某个索引的范围。换句话说，递归调用是在子域上进行的，这些子域是在它们循环到的子树的一侧"向上刷新"的。
现在，想想从那个点开始我们遇到情况4的任何时间。无论何时我们这样做，我们都知道递归将下降到的两个范围中的一个将包含一个完整子树的范围。这将立即导致我们碰到情形3，所以这个递归调用实际上不是一个真正的递归调用。这意味着情况4可以"真正"进行分支的次数最多是一次。从这一点开始，递归有效地沿着树中的一条路径继续下去。
总的来说，这意味着我们可以将完成的总功(至少是渐近地)限定为从树顶向下走两次所需的功，每个节点做O(1)功。根据需要，这将得到O(log n)的总功。
我们需要多少空间?这种扩展每个节点只使用O(1)个空间，因此所需的总空间为O(n)。
希望这对你有帮助!