Incrementing values in a search tree after insertion of a key-value pair

Question

I'm working on a programming problem and am running into a roadblock. I'm trying to come up with a data structure to map an arbitrary integer to another integer. You may be inclined to say "Hash Table!" or "Search Tree!", and I have in fact thought of these (and even tried a dirty implementation). But, there is a catch!

Every time I insert or remove a value from the mapping, I want to also increment/decrement (by one or some arbitrary offset) all values greater than or equal to the inserted/removed value.

Here's an example.

Say I have two lists of integers that I will use for my keys and values in this map:

Keys: (1, 6, 18, 21, 24)  
Vals: (2, 1,  3,  0,  4)

Now if I add a key-value pair (7, 1), I want to increment all values greater than or equal to 1 resulting in this:

Keys: (1, 6, 7, 18, 21, 24)  
Vals: (3, 2, 1,  4,  0,  5)

And subsequently if I delete the key-value pair (21, 0), this is the result:

Keys: (1, 6, 7, 18, 24)  
Vals: (2, 1, 0,  3,  4)

This is rather trivial to do with a couple of lists/arrays and some processing after each insertion/deletion (i.e., going through the values and changing them one-by-one).

But, I'm looking for a way to do it more efficiently, perhaps without having to go through the entire list of values and increment/decrementing them. Perhaps by even delaying the increment/decrement until a value (that should have been incremented/decremented) has been requested.

Any thoughts?

Answer 1

I think that if you need to do fast lookups by some key, and modify the results based on actual values, you need two data structures: one for key, one for values.

The data structure for key is going to be just an associative array (implement it as a hash-table, self-balancing tree or a skip list, it doesn't matter) from your keys to nodes in a tree for values.

The tree for values is going to be a self-balancing binary search tree (or a skip-list, see edit below). The nodes in the tree have a delta associated with them, along with their value. The delta applies to all nodes that are greater than or equal to particular node, i.e. it applies to itself and to all nodes in its right subtree.

When you insert a value, you increment the delta of all nodes bigger than or equal to the value that you are inserting. This increments the actual value of all nodes whose value is bigger than or equal to the value you are inserting in the whole tree. Deletion is similar, you just with increment replaced with decrement.

When you want to read a value, you use the key-based structure to find the node in the value-based tree. You then climb to the root (you have to keep pointers to parents of nodes in the tree for this) and accumulate delta from nodes, whose value is greater than or equal to the value in the node where you started.

You have to be careful when doing rebalancing as the self-balancing algorithm you chose requires, because you have to recalculate the deltas of some of the nodes, but this shouldn't affect the time complexity.

EDIT: For skip-list, managing the deltas is quite easy: when you are looking for a place to insert, increment delta in every node in the linked list you compare to that is greater than or equal that the value you are inserting (which also means that you are going one level down). Deletion is similar, except that you have to move any deltas the deleted item held to the right.

When you want to compute actual value of a certain node, climb as high as you can in the current item, apply the delta there (one item can have deltas from one insertion or deletion multiple times on different levels, you always have to use the value in the highest level), then go in the linked list one node to the left and repeat the process until you reach the leftmost item.

The way you are accessing the nodes also means the linked lists have to be doubly-linked.