Step 5 of 6
Prefix sums
If you'll ask "what's the sum of elements l..r?" many times, precompute prefix sums once: pre[i] is the sum of the first i elements. Then any range sum is one subtraction:
sum(l..r) = pre[r + 1] - pre[l]
O(n) setup, then O(1) per query, instead of O(n) per query. The same trick works for counts, 2D grids ("summed-area tables") and time series.
Your turn: write class RangeSum with a constructor taking the values and long long sum(int l, int r) const for the inclusive range. The test runs 200,000 queries on 200,000 values.