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

发布于 2024-12-28 15:41:34 字数 616 浏览 1 评论 0原文

我需要一个数据结构用于以下目的。假设我有一个数组a。最初所有元素都设置为零。每当我要在位置 p 处更新具有正值 new_value 的元素之一时，如果位置 p 处的原始值 old_value 是非零且大于 new_value，那么我需要更新从位置 p 开始一直到末尾的所有非零元素大批。这里的更新意味着重置该位置的旧值和新值之间较小的值。

例如，数组是： [2, 0, 3, 0, 2, 1, 5, 0, 4, 0, 7]

为位置 2 指定新值 4（从 < code>0) 具有旧值 3，我需要将数组更新为：

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

如果位置 2 的新值为 1，则结果数组为：

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

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

感谢您的建议。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

长安忆 2025-01-04 15:41:34

我相信，通过使用展开树的修改，您可以在每个元素访问或值更改的摊销 O(log n) 时间内完成此工作。该方法背后的想法是双重的。首先，我们不是将数组存储为数组，而是将其存储为一对保存原始值的数组和一个展开树，其中每个节点的键是数组的索引。例如，给定一个包含七个元素的数组，设置可能如下所示：

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

请注意，树保存数组的索引而不是数组元素本身。如果我们想查找特定索引处的值，我们只需对索引进行展开树查找，然后返回给定位置处的数组元素，这需要摊销 O(log n) 时间。

您想要支持的更改所有未来值的操作我将称为“天花板”操作，因为它为当前之后的所有值设置了上限。考虑这个问题的一种方法是，数组中的每个元素都有一个与之关联的上限（最初是无穷大），并且该元素的真实值是其真实值和上限的最小值。诀窍在于，通过使用展开树，我们可以在摊销 O(log n) 时间内调整某个点或超出某个点的所有值的上限。为此，我们通过让每个节点存储一个值 c 来扩充展开树，该值表示从该元素向前施加的上限，然后根据需要对 c 进行适当的更改。

例如，假设我们想要从某个元素向前施加一个上限。假设该元素已经位于树的根部。在这种情况下，我们只需在 O(1) 时间内将其 c 值设置为新的上限。从那时起，每当我们查找该元素处或之后的某个值时，当我们沿着树从根部走到相关元素时，我们都可以记下上限。更一般地，当我们进行查找时，每次我们跟踪右子链接时，我们都会记下该节点的 c 值。一旦我们遇到了有问题的元素，我们就知道该元素的上限，因为我们可以从我们所遵循的右子节点的根开始，获取路径上节点的最小上限。因此，为了查找结构中的元素，我们执行标准的展开树查找，跟踪我们要去的 c 值，然后输出 origins 数组值和 c 值中的最小值。

但为了使这项工作有效，我们的方法必须考虑到展开树进行旋转的事实。换句话说，我们必须展示如何在旋转期间传播 c 值。假设我们想要进行这样的旋转：

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

在这种情况下，我们不更改任何 c 值，因为在 A 之后查找的任何值仍然会通过 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”中对链接/剪切树的讨论，该论文还介绍了展开树。

希望这有帮助！

I believe that you can get this working in amortized O(log n) time per element access or value change by using a modification of a splay tree. The idea behind the approach is twofold. First, rather than storing the array as an array, we store it as a pair of an array holding the original values, and a splay tree, where each node's key is the index into the array. For example, given an array of seven elements, the setup might look like this:

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

Note that the tree holds the indices into the array rather than the array elements themselves. If we want to look up a value at a particular index, we simply do a splay tree lookup of the index, then return the array element at the given position, which takes amortized O(log n) time.

The operation you want to support of changing all future values I will call the "ceiling" operation, since it sets up a ceiling on all values after the current. One way to think about this is that each element in the array has a ceiling associated with it (which is initially infinity), and the element's true value is then the minimum of its true value and the ceiling. The trick is that by using the splay tree, we can adjust the ceiling of all values at or beyond a certain point by in amortized O(log n) time. To do this, we augment the splay tree by having each node store a value c which represents the ceiling imposed from that element forward, then make the appropriate changes to c as needed.

For example, suppose that we want to impose a ceiling from some element forward. Let's suppose that this element is already at the root of the tree. In that case, we just set its c value to be the new ceiling in O(1) time. From that point forward, whenever we do a lookup of some value that comes at or after that element, we can make a note of the ceiling as we walk down the tree from the root to the element in question. More generally, as we do a lookup, every time that we follow a right child link, we note the c value of that node. Once we hit the element in question, we know that element's ceiling because we can just take the minimum ceiling of the nodes on the path from the root whose right children we followed. Thus to look up an element in the structure, we do a standard splay tree lookup, tracking the c value was we go, then output the minimum of the origins array value and the c value.

But in order to make this work, our approach has to take into account the fact that the splay tree does rotations. In other words, we have to show how to propagate the c values during a rotation. Suppose that we want to do a rotation like this one:

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

In this case, we don't change any c values, since any value looked up after the A will still pass through the A node. However, if we do the opposite rotation and pull A above B, then we set A's c value to be the minimum of B's c value and A's c value, since if we descend into A's left subtree after performing the rotation, we need to factor B's ceiling into account. This means that we do O(1) work per rotation, and since the amortized number of rotations performed per splay is O(log n), we do amortized O(log n) work per lookup.

To complete the picture, to update an arbitrary ceiling, we splay the node whose ceiling is to be changed up to the root, then set its c value.

In short, we have O(log n) lookup O(log n) change times (amortized).

This idea is based on the discussion of link/cut trees from Sleator and Tarjan's original paper "Self-Adjusting Binary Search Trees," which also introduced the splay tree.

Hope this helps!

回复收藏 0 原文

阳光下的泡沫是彩色的 2025-01-04 15:41:34

我最初的想法有点类似于templatetypedef的答案（+1，顺便说一句），但使用简单的静态二叉树代替的八字树。就像在那个答案中一样，“逻辑”数组 L 由包含原始值和强加的二叉树 T 的实际数组 A 表示上限值。（在这种情况下，上限值树的形状是静态的，因此我们不需要跟踪树中元素的索引：对应于节点的索引就是它的索引中序遍历索引。）树可以是任何形状，只要它具有最小高度即可；也就是说，如果 L 包含 n 个元素且 2^(k-1) <= n 2^(k-1) <= n 2^k，那么树的高度应该是k。我建议将元素 2^(k-1) - 1 放在树的根部，使其左子树成为完美树包含 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 相对应的条目： if i i i i i 2^(k-1) - 1 然后在完美左子树中找到第 i 条目，如果 i = 2^(k-1) - 1 > 那么它就是根，否则从 n - (2^(k-1) - 1) 中找到第 i - (2^(k-1) - 1) 条目在右子树中递归地。

我们将所有树条目初始化为无穷大。当我们想要对 i 及之后的条目施加 c 的上限时，我们会在树中找到第 i 条目，如下所示

：我们正在查看的节点x是第i节点，或者我们需要下降到它的左子树，我们更新存储在节点中的值x 到 c 和当前值中的最小值在x。
如果我们需要下降到x的右子树，并且x中存储的当前值最多为c ，我们不需要更新树 - 它已经强制执行，所以我们可以停止。
如果 x 是第 i 个节点，我们就可以停止。

这就是设置上限的全部内容。请注意，A 本身永远不会更新。

如果我们想查找L的第i值，那么我们将局部变量c初始化为无穷大并找到i根据以下规则，树中的第 条目：

如果我们正在查看的节点 x 是第 i 节点，或者我们需要下降到其< em>右子树，然后将c设置为最小值其当前值和存储在x中的值。
如果 x 是第 i 个节点，我们就可以停止。

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

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

My initial idea was somewhat similar to templatetypedef's answer (+1, by the way), but using a simple static binary tree instead of a splay tree. Like in that answer, the 'logical' array L is represented by an actual array A containing the original values and a binary tree T of imposed ceiling values. (In this case the shape of the tree of ceiling values is static, and thus we don't need to keep track of the indices of elements in the tree: the index corresponding to a node is simply its in-order traversal index.) The tree can be any shape as long as it has minimal height; that is, if L is to contain n elements and 2^(k-1) <= n < 2^k, then the tree should have height k. I would suggest a layout where we put element 2^(k-1) - 1 at the root of the tree, make its left subtree a perfect tree containing L[0 .. 2^(k-1) - 2], and define its right subtree recursively for L[2^(k-1) .. n - 1] (that is, it may be empty). For example, a 12 element tree would have entries as follows:

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

(Note that these numbers are not the entries of the tree - they just indicate what position in the array the entries of the tree correspond to.) This description also gives the algorithm for finding the entry in the tree that corresponds to entry i out of n: if i < 2^(k-1) - 1 then find the ith entry in the perfect left subtree, if i = 2^(k-1) - 1 then it's the root, and otherwise find the i - (2^(k-1) - 1)th entry out of n - (2^(k-1) - 1) in the right subtree recursively.

We initialize all tree entries to infinity. When we want to impose a ceiling of c to entry i and later, we find the ith entry in the tree as follows:

If the node x that we are looking at is the ith node or we need to descend into its left subtree, we update the value stored at node x to the minimum of c and the current value at x.
If we need to descend into the right subtree of x and the current value stored at x is at most c, we don't need to update the tree - it's already enforced, so we can stop.
If x is the ith node, we can stop.

That's all for imposing a ceiling. Note that A itself is never updated.

If we want to look up the ith value of L, then we initialize a local variable c to infinity and find the ith entry in the tree according to these rules:

If the node x that we are looking at is the ith node or we need to descend into its right subtree, then set c to the minimum of its current value and the value stored at x.
If x is the ith node, we can stop.

Now we return the minimum of A[i] and c.

Both of these operations are O(log n) (actual time for each operation, not amortized). For implementation, note that you can use an array to hold the binary tree.

回复收藏 0 原文

请持续率性 2025-01-04 15:41:34

我相信笛卡尔树可以帮助您解决问题。与维基百科中描述的唯一区别是，我建议您在每个节点中构建最大堆而不是最小堆（即将属性更改为每个节点的值不小于它的子节点）。
您需要转到当前节点的右子节点，并沿着树向下更改所有值大于新值的元素。您可以证明，通过这种方式，您将检查不超过 3*K 个元素，其中 K 是需要更改的实际元素数。另一个好处是，通过执行您描述的操作，当您更改所有大于新值的值时，每个顶点中的堆属性仍将保留。

希望这个答案有帮助。

回复收藏 0 原文

~没有更多了~