# Update and find-smallest-absolute-value operations on a tree

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.

• Nice question! What are your thoughts on it? – Yuval Filmus Sep 20 '17 at 13:11
• 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? – D.W. Sep 21 '17 at 17:57
• 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. – Vk1 Sep 22 '17 at 16:05