QTREE - Complexity

Preprocessing takes $O(n)$ to build the tree structure and perform HLD decomposition. Building the segment tree takes $O(n)$. Each QUERY walks $O(\log n)$ chains and does $O(\log n)$ work per chain via segment tree queries, giving $O(\log^2 n)$ per query.

Each CHANGE is a single segment tree point update, taking $O(\log n)$ time. Total time: $O(n + q \log^2 n)$, which handles the constraints comfortably.

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