Problem - Subtree Queries

You are given a tree of $n$ nodes. Each node has a value. Two types of queries: update a node's value, or ask for the sum of all values in a node's subtree. Brute force: traverse the subtree for every query. That is $O(n)$ per query, too slow for $n \le 2 \cdot 10^5$ and $q \le 2 \cdot 10^5$ queries.

Euler tour converts this into a range query problem. The range representation means you can use efficient range query structures to answer subtree questions in logarithmic time.

Space complexity is $O(n)$ for the data structures used.