March 24
Prefix Sum
What prefix sum means, when precomputing cumulative values turns expensive range queries into cheap answers.
What it is
Prefix sum is a way to precompute the running total of an array.
That way, instead of summing a range from scratch every time, you answer it from the difference between cumulative values.
When to use it
It appears when:
- there are many range sum queries
- the array does not change constantly
- you want to trade preprocessing for faster answers
Common mistake
The classic mistake is memorizing the formula without understanding the gain.
The formula is not the point.
The point is turning many O(n) sums into O(1) queries.
Better question
Before using it, ask:
- will I query many intervals?
- is preprocessing worth it?
- does the structure change so often that the cumulative data becomes useless?
Share this page
Copy the link manually from the field below.