updating n elements in $O(\lg{n})$ time

Question

I need to devise a data structure $S$ with the following functions:

• BUILD($S$) - build the data structure from a series of $n$ elements in time $O(n \lg{n})$
• INSERT($S$, $k$) - insert a new element with the key $k$ to $S$ in time $O(\lg{n})$
• DELETE($S$, $p$) - delete the element $p$ from $S$ in time $O(\lg{n})$
• D-SUCCESSOR($S$, $p$, $d$) - return the $d$-successor of $p$ in time $O(\lg{n})$ where $d$-successor of $p$ is the $d$-th element after $p$ if the elements where ordered by their key
• DECREASE-UPTO($S$, $k$, $val$) - decrease by $val$ all keys in $S$ where the key is not larger than $k$, in $O(\lg{n})$ time

---

I've managed to do the first 4 points using order static tree, as an extension of red black tree, but I'm having trouble with the last one, assuming $k$ is bigger than all elements in $S$ the function will need to update the values of all $n$ elements in $S$ how can this be done in $O(\lg{n})$ time?

Answer 1

The idea is to maintain a balanced BST where each node is suitably augmented with satellite information, as you have already done for the first 4 points.

To handle the last point you just need to add a new field $\delta(v)$ to each node $v$. The meaning of this field is as follows:

If $u$ is a vertex of the tree, the key stored in $u$ is $k(u)$, and $\langle r = u_1, u_2, \dots, u_\ell = u \rangle$ is the path from the root $r$ of the tree to $u$ then the key $k^*(u)$ that is logically represented by $u$ is: $$ k^*(u) = k(u) + \sum_{i=1}^\ell \delta(u_i). $$

This fields can be maintained while the other operations are performed, while preserving the BST order of the represented keys in the tree. I.e., if $v$ is the left (reps. right) child of $u$ then $k^*(v) < k^*(u)$ (resp. $k^*(v) > k^*(u)$).