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?

  • $\begingroup$ "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$ $\endgroup$ Jul 7, 2021 at 18:04
  • $\begingroup$ I'd start with (5). Since there are up to n values to change, this can happen in O(log n) only if you design a data structure so you can make a small (log n) modification to your data that can affect n values. So your data must be stored in some distributed way. $\endgroup$
    – gnasher729
    Aug 4 at 16:50

1 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)$).

  • $\begingroup$ 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 $\endgroup$ Jul 7, 2021 at 18:25
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 7, 2021 at 18:53
  • $\begingroup$ In your specific example, if $r$ is the root vertex, you only need to decrease $\delta(r)$ by $1$. $\endgroup$
    – Steven
    Jul 7, 2021 at 19:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.