Pattern Recognition Drill
Easy Arrays & Strings
The Problem
Given array a, answer multiple range-sum queries [l, r] efficiently.
What approach would you use?
Think about it before scrolling down.
Build prefix array in O(n). Each query: prefix[r+1] - prefix[l] in O(1).
Only works for consecutive queries of same length. Prefix sum handles arbitrary ranges.
Common Trap
Summing the range each time is O(n) per query → O(n*q) total. Prefix sum makes it O(n + q).