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 $a$ of length $n$ . We build an auxiliary array pref where pref[i] stores the sum of the first i elements.

The recurrence is:

$pref_i = pref_{i-1} + a_i$

Prefix sums

Introduction

Idea

Algorithm

Example 1: Sum on a Segment

Suffix Sums

Prefix Operations

Two-Dimensional Prefix Sums

Example 2: Range Sum Queries