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:
Delete every pair $(k_i, v_i)$ such that $a-C \le k_i \le b-C$.
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.