2
$\begingroup$

I'm required to describe an implementation of a data structure that holds key,value pairs, which can be signed integers.

We need to be able to init() in O(1), insert(x) in O(logn), delete(x) in O(logn) and sumPrevious(x), which returns sum of values of the keys that are smaller than key 'x', in O(logn). An AVL rank tree, which rank is sum of values in sub-tree, should do the trick. So far so good.

Now I need to also implement maxSumPrevious(), which returns the key 'k' for which 'sumPrevious(k)' is maximal, in O(1). This is where I got stuck. Since inserting or deleting an element changes the 'sumPrevious' of ALL the elements bigger than it. I tried going in the direction of a different rank that updates in insertion/deletion, but it lead to nowhere.

Thank you in advance

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you credit the original source where you saw this problem? $\endgroup$
    – D.W. ♦
    Sep 20, 2022 at 18:14
  • $\begingroup$ Let maxSumPrevious(n) be the max prefix sum in the subtree $n$. For a node $n$ with children $\ell$ and $r$, $maxSumPrevious(n) = \max(maxSumPrevious(\ell), sum(\ell) + maxSumPrevious(r))$. $\endgroup$
    – Dmitry
    Sep 20, 2022 at 18:18
  • 1
    $\begingroup$ @Dmitry, clever! That sounds like the main idea of a solution, i.e., an answer. Perhaps write that as an answer rather than as a comment, so we can upvote it? I think it's better to have that in an answer, even if it is very concise, than a comment. $\endgroup$
    – D.W. ♦
    Sep 20, 2022 at 18:24
  • $\begingroup$ @D.W. Taken from one of my uni exams in data structures $\endgroup$
    – sadcat_1
    Sep 20, 2022 at 18:51

1 Answer 1

Reset to default
2
$\begingroup$

You just need to add some additional data in each node, namely:

  • the maximum sum of values of previous nodes in the subtree;
  • the key in the subtree that reach this maximum sum.

It is clear that with this data, you can get maxSumPrevious() in $\mathcal{O}(1)$ time, but you would need to update the insertion and deletion of a node.

I will try to give details for insertion, deletion is done in similar ways. Suppose then that you want to insert $(k, v)$ in a tree $T$:

  • if $T$ is empty, create a single node x such that x.MSPV = 0 (MSPV stands for "max sum previous values") and x.keyMSPV = k;
  • otherwise, make an usual insertion in BBST, and for each modified node x (by insertion in one child of x or after a rotation):
    • x.MSPV is the largest among the following:
      • x.left.MSPV if the corresponding key is in the left child;
      • x.left.sumValues if the corresponding key is in the root x;
      • x.left.sumValues + v + x.right.MSPV if the corresponding key is in the right child.
    • x.keyMSPV can be updated depending on the key that defines x.MSPV.

Those additional operations are done in $\mathcal{O}(1)$ time for each node, so the total complexity stays $\mathcal{O}(\log n)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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