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

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?

• "in $O(lg{n})$" means the time complexity of the function needs to be $O(lg{n})$. $N$ and $n$ both mean the number of elements in $S$ Jul 7 at 18:04

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)$$).
• how does this allow me to update all keys smaller or equal a given $k$ by a given value? All I can see is that now I have a field that sum the total route from the root to a given node. If I have a tree with 2 at its root, 1 the left son and 3 the right and I call DECREASE-UPTO with $k=3$ and $val=1$ I now have a tree with 1 as root 0 is left son and 2 is right son, but I don't see how does your answer give me this result Jul 7 at 18:25
• Let $v$ be a vertex of your BST and let $T_v$ be the subtree rooted at $v$. To decrease by $x$ the value of all the keys stored in $T_v$ you only have to decrement $\delta(v)$ by $x$, which requires $O(1)$ time. Moreover, given any value $k$, you can find a collection of $O(\log n)$ vertex-disjoint subtrees or single vertices of your BST that contain all keys that are not larger than $k$. This can be done in $O(\log n)$ time. Once this is done, you only need to update $O(\log n)$ keys and fields $\delta(\cdot)$ which, by the above discussion, takes $O(\log n)$ overall time. Jul 7 at 18:53
• In your specific example, if $r$ is the root vertex, you only need to decrease $\delta(r)$ by $1$. Jul 7 at 19:00