Thanks for the clarification. I've accepted your answer as I have convinced myself of the details. Both the reduction to balanced binary trees and the left/right bit encoding are really cool ideas that I wouldn't have come up with by myself. Thank you so much!

Thanks for the thorough answer! I am not sure how you "change a heavy path of length $k$ into a binary tree of depth $O(\log k)$, with each original node (and its sum) being the sum of $O(\log k)$ new nodes". As far as I understand it, in (1) you reduce the problem on general forests to the problem restricted to balanced binary trees, and (2)-(3) solve the problem for balanced binary trees. However I don't understand the reduction in step (1). Can you elaborate on that?

Can you clarify what you mean by "almost affine"? You mention disk footprint - how is the input f represented? Is f represented as a list of |X| values, i.e. you're looking for some compression method? Or is f represented by its "almost affine" pieces, i.e. you're looking for a searching method?