1
$\begingroup$

I have a balanced binary tree that stores a number in each node, initially zero. I want to build a data structure that will support the following two operations:

  1. Given a vertex $v$ in the tree and a real value $w$, add $w$ to all nodes in the subtree under $v$.

  2. Given a vertex $v$ in the tree, find the smallest absolute value associated with any node in the subtree of $v$.

The shape of the tree is static and remains unchanged. No new vertices can be added. We don't need to support any other operations (e.g., insert a node, delete a node, lookup the value in a node).

I want the running time of both operations to be $O(\lg n)$, where $n$ is the number of nodes in the tree. How can I do that? Recursively visiting all nodes in the subtree would be too slow, as it would take $O(n)$ time.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Nice question! What are your thoughts on it? $\endgroup$ – Yuval Filmus Sep 20 '17 at 13:11
  • $\begingroup$ Are there any constraints on the space usage of the data structure? What's the source of the problem? Do you have a reason to believe both operations can be supported in $O(\lg n)$ time? Are you OK with an amortized running time? $\endgroup$ – D.W.♦ Sep 21 '17 at 17:57
  • $\begingroup$ no space restrictions, fine with amortized running time. Normal min or max of subtree can be supported in $O(\lg n)$, so I believe this might also be possible in same time. $\endgroup$ – Vk1 Sep 22 '17 at 16:05

Your Answer

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

Browse other questions tagged or ask your own question.