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.

  • $\begingroup$ 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. $\endgroup$ – Jeffε Nov 12 '12 at 7:03
  • $\begingroup$ 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? $\endgroup$ – Nullptr Dev Nov 14 '12 at 6:32
  • 1
    $\begingroup$ Can you give a general description of the update you want to support instead of just examples? $\endgroup$ – Jeffε Nov 14 '12 at 7:48
  • $\begingroup$ I updated my question. $\endgroup$ – Nullptr Dev Nov 14 '12 at 18:07
  • 1
    $\begingroup$ 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? $\endgroup$ – Jeffε Nov 14 '12 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.