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:
