用于修整数组中较大值的数据结构？

Question

我需要为以下目的有一个数据结构。假设我有一个数组a。最初所有元素都设置为零。无论何时我要更新位置p上正数值new_value中的一个元素，如果位置pold_value上的原始值不为零并且大于new_value，那么我需要更新从位置p开始的所有非零元素一直到数组的末尾。这里的更新意味着将该位置的旧值与new_value之间的较小值重新设置。

例如，该阵列是： [2, 0, 3, 0, 2, 1, 5, 0, 4, 0, 7]

鉴于4对于具有一个旧值3位置2（从0开始）的新值，我需要更新所述阵列为：

[2, 0, 3, 0, 2, 1, 4, 0, 4, 0, 4]

如果在位置2的新值是1，则所得到的数组是：

[2, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]

有没有已知的数据结构可以有效地做到这一点？我需要很多这样的更新操作。

谢谢您的建议。

Answer 1

我相信Cartesian tree可能会帮助你解决你的问题。与维基百科中描述的唯一区别在于，我建议您在每个点头中构建最大堆而不是最小堆（即，将属性更改为每个节点的值不小于它的子节点）。 您需要转到当前节点的右侧子节点，并沿树形结构向下，更改所有值大于新值的元素。你可以证明这种方式你不会再检查3 * K元素，其中K是需要改变的元素的实际数量。另一件好事是，通过执行描述每个顶点堆属性的操作仍将保留，因为您更改了全部的值大于新值。

希望此回答有帮助。

Answer 2

我相信你可以通过使用splay树的修改，使每个元素访问或值更改的分期O（log n）时间得到这个工作。这种方法背后的想法是双重的。首先，我们不是将数组存储为数组，而是将它作为一对保存原始值的数组和一个splay树进行存储，其中每个节点的键都是数组中的索引。例如，假定七个要素的数组，设置可能是这样的：

Array: 3 1 4 2 5 9 3 
Tree:    3 
       / \ 
       1. 5 
      /\./\ 
      0. 2 4. 6 

注意的是，这棵树上的索引到数组，而不是数组元素本身。如果我们想在特定的索引处查找一个值，我们只需对索引进行splay tree查找，然后返回给定位置处的数组元素，这需要分摊O（log n）时间。

您希望支持更改所有未来值的操作我将称之为“天花板”操作，因为它会在当前所有值之后设置一个上限。考虑这一点的一种方式是数组中的每个元素都有一个与之相关的天花板（最初是无限的），而元素的真实值则是其真实值和天花板的最小值。诀窍是，通过使用splay树，我们可以通过分摊的O（log n）时间来调整所有值的上限。为此，我们通过让每个节点存储代表从该元素向前施加的上限的值c来扩充splay树，然后根据需要对c进行适当的更改。

例如，假设我们想从某个元素向前施加一个上限。假设这个元素已经在树的根部。在这种情况下，我们只需将它的c值设置为O（1）时间的新上限。从这一点开始，每当我们查看某个元素之后或之后的某个值时，我们就可以记下从树根到元素的树状结构。更一般地说，当我们进行查找时，每次我们遵循一个正确的子链接时，我们都会注意到该节点的c值。一旦我们触及到元素的问题，我们就知道元素的上限，因为我们可以从我们遵循的正确子节点的根目录获取路径上节点的最小上限。因此，为了查找结构中的元素，我们执行标准的splay树查找，跟踪我们去的c值，然后输出原始数组值和c值的最小值。

但是为了做到这一点，我们的方法必须考虑到splay树的旋转这一事实。换句话说，我们必须展示如何在旋转过程中传播c值。假设我们想要做这样一个旋转：

A.   B 
    /.  ->. \ 
    B.    A 

在这种情况下，我们不改变任何C值，因为任何价值抬头在A后仍然会通过的节点。然而，如果我们进行相反的旋转并将A拉到B以上，那么我们将A的c值设置为B的c值和A的c值的最小值，因为如果我们在执行旋转后下降到A的左子树中，则需要因子B的上限考虑在内。这意味着我们每轮执行O（1）次工作，并且由于每次展开所执行的已分摊循环次数为O（log n），因此我们会对每次查找进行分摊O（log n）工作。

要完成图片，要更新任意天花板，我们展示其上限要更改为根的节点，然后设置其c值。总之，我们有O（log n）查找O（log n）更改时间（摊销）。

这个想法是基于来自Sleator和Tarjan的原创论文“Self-Adjusting Binary Search Trees”的链接/剪切树的讨论，该文章还介绍了splay树。

希望这会有所帮助！

Answer 3

我最初的想法有点类似于templatetypedef's answer（+1，顺便说一句），但是使用了一个简单的静态二叉树而不是一个splay树。就像在该答案中那样，'逻辑'数组L由实际数组A表示，其包含原始值和强制上限值的二叉树T。 （在这种情况下，最大值树的形状是静态的，因此我们不需要跟踪树中元素的索引：对应于节点的索引就是它的有序遍历索引）只要树的高度最小，树就可以是任何形状;也就是说，如果L包含n元素和2^(k-1) <= n < 2^k，那么该树应具有高度k。我会建议一个布局，我们将元素2^(k-1) - 1放在树的根部，使其左子树perfect树包含L[0 .. 2^(k-1) - 2]，并递归地为L[2^(k-1) .. n - 1]（即它可能为空）定义其右子树。例如，一个12元素树将有条目如下：

   7 
     /-----/ \-----\ 
     3    11 
    /-/ \-\   /-/ 
    1  5  9 
/\ /\ /\ 
0 2 4 6 8 10 

（请注意，这些数字是不是树的条目 - 他们只是表明什么位置阵列中的树的条目对应。）此说明还给出了查找树中对应于n中的条目i的条目的算法：如果i < 2^(k-1) - 1则在完美左子树中找到i th条目，如果i = 2^(k-1) - 1那么它是根，否则找到i - (2^(k-1) - 1) th条目在右子树中递归地输出n - (2^(k-1) - 1)。

我们将所有树条目初始化为无穷大。当我们要处以c天花板进入i后来，我们发现在树中i个条目，如下所示：

• 如果我们要寻找的节点x是i个节点或我们需要下降到左边的子树，我们将存储在节点x中的值更新为最小值c和当前值x。
• 如果我们需要陷入的x的右子树并保存在x当前值最多c，我们并不需要更新树 - 它已经执行的，所以我们可以停下来。
• 如果x是第i节点，我们可以停止。

这都是为了施加上限。请注意，A本身从不更新。

如果我们要查找的L的i个值，然后我们初始化一个局部变量c到无穷远，并找到在树中i个条目根据这些规则：

• 如果节点x我们正在查看的是第i th节点，或者我们需要下降到右边的子树，然后将c设置为其当前值的最小值以及存储在x处的值。
• 如果x是第i节点，我们可以停止。

现在我们返回最小值A[i]和c。

这两个操作都是O(log n)（每个操作的实际时间，不是摊销）。为了实现，请注意，您可以使用数组来保存二叉树。