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:
Given a vertex $v$ in the tree and a real value $w$, add $w$ to all nodes in the subtree under $v$.
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.