<p>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 &lt; 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:</p>

<ol>
<li><p>Delete every pair $(k_i, v_i)$ such that $a-C \le k_i \le b-C$.</p></li>
<li><p>Replace every pair $(k_i, v_i)$ such that $a\le k_i\le b$ with the pair $(k_i-C,v_i)$.</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-11-12T07:03:05.023Z
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.
Jeffε
CC BY-SA 3.0
2012-11-14T06:32:56.537Z
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
CC BY-SA 3.0
2012-11-14T07:48:55.930Z
Can you give a general description of the update you want to support instead of just examples?
Jeffε
CC BY-SA 3.0
2012-11-14T18:07:12.807Z
I updated my question.
Nullptr Dev
CC BY-SA 3.0
2012-11-14T22:33:18.927Z
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?
Jeffε
<ds.algorithms><ds.data-structures>
Efficient update of the keys in associative container
Nullptr Dev
# Efficient update of the keys in associative container

(Asked by: username_0 on 2012-11-02)

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.

**Tags:** ds.algorithms, ds.data-structures
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: Can you give a general description of the update you want to support instead of just examples?  
> **username_0**: I updated my question.  
> **username_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?  

---

## 0 answers

