Approach Summary
Precompute prefix sums. Query sum(l, r) = prefix[r+1] - prefix[l] in O(1).
How to Recognize This Pattern
- Many range queries on a fixed array
Complexity Analysis
Time Complexity
O(1) query
Space Complexity
O(n)
Tags
Array Design Prefix Sum