Foundations -> Prefix Sums¶

Turn many range questions into subtraction of precomputed aggregates, then layer counting tricks on top.

Microtopics¶

Source	Type
USACO Guide intro prefix sums	`Reference`
USACO Guide more prefix sums	`Reference`
OI Wiki prefix sum and adjacent difference	`Reference`

Source	Type
CSES Problem Set	`Practice`

Material	Type
Foundations cheatsheet	`quick reference`
Static Range Sum Queries note	`anchor note`
Templates overview	`template guide`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Static Range Sum Queries	`CSES`	`Easy`	-	Implementation-Heavy	Prefix Sums; Indexing; Arrays	Range-Sum; Prefix-Sum; Range-Query; Precompute	The simplest possible range-sum baseline for learning prefix preprocessing.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Range Xor Queries	`CSES`	`Easy`	-	-	-	Prefix-XOR; Range-Query; Bitwise	Same template, but with xor accumulation.
Subarray Sums I	`CSES`	`Medium`	-	Implementation-Heavy	Prefix Sums; Positive Arrays; Sliding Window	Two-Pointers; Subarrays	A classic positive-array sliding-window problem that is really prefix sums in disguise.
Subarray Sums II	`CSES`	`Medium`	-	Implementation-Heavy; Math-Heavy	Prefix Sums; Hash Maps; Counting	Hash-Map; Subarrays	A standard prefix-sum counting problem that generalizes the idea beyond positive numbers.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Subarray Divisibility	`CSES`	`Medium`	-	Math-Heavy	Prefix Sums; Modular Arithmetic; Frequency Counting	Mod Arithmetic; Counting	A canonical prefix-sum-plus-modulo benchmark that shows why equal remainders matter.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Forest Queries	`CSES`	`Medium`	-	Modeling-Heavy; Query-Heavy	Prefix Sums; 2D Grids; Rectangle Inclusion-Exclusion	2D Prefix Sums; Rectangles; Rectangle-Query; Grid	A great 2D prefix-sum benchmark with a very reusable inclusion-exclusion pattern.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`CVP00001`	Ô ăn quan	`secondary`	`hard`	circular updates; range-add point-query; query-from-initial-state	Note	Code
`PREFIXSUMADDICTS`	Prefix Sum Addicts	`secondary`	`medium`	suffix prefix differences; sorted sequence feasibility; first block capacity bound	Note	Code
`STATICRANGESUMQUERIES`	Static Range Sum Queries	`primary`	`easy`	prefix sum build; range sum by subtraction; immutable array queries	Note	Code

python3 scripts/generate_problem_catalog.py