Range Sum I - Analysis

Compare approaches: Segment tree: $O(\log n)$ per operation, total $O(q \log n)$ Sqrt decomposition: $O(\sqrt{n})$ per query, $O(1)$ per update For $n = q = 2 \cdot 10^5$: segment tree does about $3.4 \cdot 10^6$ operations, sqrt does about $8.9 \cdot 10^7$ query operations plus $q$ update operations.

Both work here. Segment trees are faster asymptotically, but sqrt decomposition is simpler to implement. In contests, simpler often means fewer bugs.