Data structure for trimming large values in an array?

Question

I need to have a data structure for the following purposes. Let's say I have an array a. Initially all elements are set to zero. Whenever I am to update one of the elements with a positive value new_value at position p, if the original value at position p old_value is non-zero and is larger than new_value, then I need to update all non-zero elements starting from position p all the way to the end of the array. Here update means reset the values with the smaller one between the old value at that position and new_value.

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

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

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

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

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

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

Thank you for your suggestions.

Answer 1

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.

Answer 2

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!

Answer 3

I believe a Cartesian tree may help you with your problem. The only difference with the one described in wikipedia is that I advice you to build max heaps instead of min heaps in each nod(i.e. change the property to the value of each node is not smaller than both it's children). You need to go to the right child of the current node and descend down the tree changing all elements with values greater then new value. You can prove that this way you will check no more then 3*K elements where K is the actual number of elements that need to be changed. Another good thing is that by performing the operation you describe the heap property in each vertex will still be kept as you change all the values greater then the new value.

Hope this answer helps.