Build a running-total array once, then answer any range-sum query in O(1). The simplest technique that feels like cheating.
What Is It?
Prefix sum is a precomputed array where pref[i] = sum of the first i elements. Once built in O(n), any range sum [l..r] is just pref[r+1] - pref[l] — two lookups, O(1).