I was trying to solve this problem from the gym and I struggled to find the solution. Finally I came up with a very interesting data structure capable of handling any subtree update and really don't know if someone else has seen it before, but I will post it here since I could find its name (if it has) in google. My solution was able to solve the problem with O(N) memory, O(N) in creation, O(sqrt(N)) per query. When I saw the editorial I saw that it had another interesting approach with an update buffer which solved the problem in O(Q*sqrt(Q)*log(N)), for my surprise my solution was O(Q*sqrt(N) + N) summing the creation and queries, and I saw conveniently Q was 10^4 so probably the author didn't knew about my approach.