Prefix sums
How to build prefix sums
Introduction
Prefix sums are one of the most fundamental techniques in competitive programming. They help us answer range queries efficiently, precompute useful information, and turn many brute-force ideas into fast solutions.
The main idea is simple: instead of recomputing sums for every query, we build cumulative values once and reuse them whenever needed.
Idea
Suppose we have an array of length . We build an auxiliary array pref where pref[i] stores the sum of the first i elements.
The recurrence is: