Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I need to maintain a set $\langle(k_1, v_1), (k_2, v_2), \dots, (k_N, v_N)\rangle$ of key-value pairs subject to the following update operation. Given two keys $a < b$ and a "shift" value $C$ as input, an update first deletes all pairs whose keys are in the range $[a-C, b-C]$ and then shifts all keys in the range $[a,b]$ downward by $C$. More explicitly:

  1. Delete every pair $(k_i, v_i)$ such that $a-C \le k_i \le b-C$.

  2. Replace every pair $(k_i, v_i)$ such that $a\le k_i\le b$ with the pair $(k_i-C,v_i)$.

How can I support this update operation efficiently? I would prefer an algorithm that performs the update "in-place" instead of allocating and deallocating temporary memory.

share|improve this question
It's unclear what an "update" operation is supposed to do, or even how to specify the operation. (Did you describe one update or three? Why was 25 removed? Why are there not two 40s after the update(s)?) But if my guess is correct, almost any balanced binary tree could be modified to perform an update in O(log n) time. – JɛffE Nov 12 '12 at 7:03
Yes, it was not clear indeed. This example should make it better. Let's have AC {(10, A), (20, B), (25, C), (40, D), (50, E), (60, F), (80, G), (90, H), (100, I), (200, J)}. I would like to get the following result: {(10, A), (20, G), (30, H), (40, I), (50, E), (60, F), (200, J)}. That's I would like to delete all elements with keys between 20=(80-60) and 40=(100-60) and then update the with keys between 80 and 100 by decreasing them with 60. I am trying to avoid additional memory allocations because it is slow operation. I am trying to do my updates "in-place". How can I do it efficiently? – Nullptr Dev Nov 14 '12 at 6:32
1  
Can you give a general description of the update you want to support instead of just examples? – JɛffE Nov 14 '12 at 7:48
I updated my question. – Nullptr Dev Nov 14 '12 at 18:07
1  
Major rewrite. Please check that I did not change the intent of the question. It's not clear from your problem statement what other operations you want the data structure to support. Insert a new record? Delete a record? Look up the value associated with a given key? Look up the key associated with a given value? – JɛffE Nov 14 '12 at 22:33

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.