Level 1 · FoundationsBUILD YOUR INTUITION
Prefix Sum
Store the sum of each prefix so an inclusive range can be expressed as the difference of two prefixes.
THE MENTAL MODELWhen should this come to mind?
Store the sum of each prefix so an inclusive range can be expressed as the difference of two prefixes.
Many range-sum queriesRepeated sums over immutable inputSubarray totals What makes it work
Use a leading zero and answer [left, right] with prefix[right + 1] − prefix[left]. Negative numbers are allowed.
When to choose something else
Frequent updates make rebuilding a prefix array expensive; use a data structure designed for updates.
See the pattern in action
Change the input. Follow the state. Make it yours.