Preprocessing takes O(n) to build the tree structure and perform HLD decomposition. Building the segment tree takes O(n). Each QUERY walks O(logn) chains and does O(logn) work per chain via segment tree queries, giving O(log2n) per query.
Each CHANGE is a single segment tree point update, taking O(logn) time. Total time: O(n+qlog2n), which handles the constraints comfortably.
Space complexity is O(n) for the data structures used.