Data structure for trimming large values ​​in an array?

Question

I need a data structure for the following purposes. Say I have an array a . Initially, all elements are set to zero. Whenever I have to update one of the elements with a positive value of new_value at position p , if the original value at position p old_value non-zero and greater than new_value , then I need to update all non-zero elements from position p to the end array. Here, updating means resetting values ​​with a lower value between the old value at this position and new_value .

For example, an array: [2, 0, 3, 0, 2, 1, 5, 0, 4, 0, 7]

Given the new value of 4 for position 2 (starting at 0 ), which has the old value of 3 , I need to update the array:

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

If the new value at position 2 is 1, then the resulting array:

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

Is there a known data structure that can do this efficiently? I need a lot of such update operations.

Thanks for your suggestions.

Answer 1

I believe that you can get this to work in amortized O (log n) time to access an element or change a value using a splay tree modification. The idea of ​​the approach is twofold. First, instead of storing the array as an array, we save it as an array pair containing the original values, and a splay tree, where each node key is an index in 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 contains indexes in the array, not the elements of the array themselves. If we want to find the value in a specific index, we simply search the index of the splay tree by index, and then return the array element to the given position, which requires depreciation of O (log n).

The operation you want to support to change all future values ​​I will call the operation "ceiling", as it sets the ceiling for all values ​​after the current one. One way to think about this is that each element in the array has a ceiling associated with it (which is initially infinite), and the true value of the element is the minimum value of its true value and ceiling. The trick is that, using the splay tree, we can adjust the ceiling of all values ​​at a certain point or outside as a result of the depreciation of O (log n). To do this, we expand the splay tree, saving at each node the value of c, which represents the ceiling superimposed on this element forward, and then, if necessary, make the appropriate changes to c.

For example, suppose we want to impose a ceiling from an element forward. Assume that this element is already in the root of the tree. In this case, we simply set the value of c for the new ceiling O (1) times. From this point of view, whenever we look at some value that comes into this element or after it, we can record the ceiling when we go down the tree from the root to the element in question. More generally, when we do a search, every time we follow the correct child link, we mark the value c of this node. As soon as we click on the element in question, we know this ceiling of the element, because we can just take the minimum ceiling of the nodes on the way from the root, whose right children we followed. Thus, to find an element in the structure, we perform a standard search in the splay tree, tracking the value of c, we send, then we print the minimum value of the value of the original value and the value of c.

But in order to make this work, our approach must take into account the fact that the splay tree makes rotations. In other words, we need to show how to propagate the values ​​of c during rotation. Suppose we want to make this turn:

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

In this case, we do not change any values ​​of c, since any value looked after A passed through A node anyway. However, if we do the opposite rotation and extend A above B, then we set the value of A c to at least the value of B c and the value of A c, because if we go down to the left subtree after the rotation, we need B of the ceiling. This means that we perform O (1) per rotation, and since the amortized number of revolutions performed for each playback is O (log n), we amortise O (log n) for each search.

To complete the image, to update an arbitrary ceiling, we will display a node whose ceiling should be changed to the root, and then set its value to c.

In short, we have O (log n) search O (log n) change time (amortized).

This idea is based on a discussion of the link / cut-out trees from the original paper by Slator and Tarjan, “Self-Regulating Binary Search Trees,” which also presents a play tree.

Hope this helps!

Answer 2

My initial idea was a bit like a templatetypedef answer (+1 by the way), but using a simple static binary tree instead of a splay tree. As in this answer, the “logical” array L is represented by the actual array A containing the original values ​​and the binary tree T of ceiling values. (In this case, the shape of the ceiling value tree is static, and therefore we do not need to track the indices of the elements in the tree: the index corresponding to the node is simply its traversal index.) The tree can be of any shape if it has a minimum height; that is, if L contains n elements and 2^(k-1) <= n < 2^k , then the tree must have height k . I would suggest a layout in which we put the element 2^(k-1) - 1 in the root of the tree, make its left subtree perfect tree, containing L[0 .. 2^(k-1) - 2] , and recursively define its right subtree for L[2^(k-1) .. n - 1] (that is, it can be empty). For example, in a tree of 12 elements, the following entries will be entered:

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

(Note that these numbers are not tree entries — they simply indicate which position in the array corresponds to the tree entries). This description also gives an algorithm for finding a record in the tree corresponding to the input i from n : if i < 2^(k-1) - 1 , then find the i th element in an ideal left subtree, if i = 2^(k-1) - 1 , then this is the root, and otherwise it will find the i - (2^(k-1) - 1) -th input from n - (2^(k-1) - 1) in the correct subtree recursively.

We initialize all tree entries ad infinitum. When we want to overlay c on i and later, we find i th in the tree as follows:

• If the node x we are looking at is i th node, or we need to go down to its left subtree, we will update the value stored in node x to a minimum of c and the current value in x .
• If we need to go down to the right subtree x , and the current value stored in x is not more than c , we do not need to update the tree - it is already running, so we can stop it.
• If x is i th node, we can stop.

It’s all for ceiling. Note that A itself is not updated.

If we want to find the i value of L , then we initialize the local variable c to infinity and find the ith element in the tree in accordance with these rules:

• If the node x we are looking at is i th node, or we need to go down to its right subtree and then set c to at least its current value, and the value is stored in x .
• If x is i th node, we can stop.

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

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

Answer 3

I believe that the Cartesian tree can help you solve your problem. The only difference from the one described on Wikipedia is that I advise you to create maximum heaps, not minimum heaps in each nod (i.e. change the property to the value of each node no less than both of its children). You need to go to the right child of the current node and go down the tree, changing all elements with values ​​exceeding the new value. You can prove that in this way you will check no more than 3 * K elements, where K is the actual number of elements that need to be changed. Another thing is that, performing the described operation, the heap property at each vertex will be preserved when all values ​​exceeding the new value are changed.

Hope this answer helps.