Foundations -> Difference Arrays¶

A range-update perspective on prefix sums: store changes at boundaries, then recover the real array by taking prefixes.

Microtopics¶

Source	Type
OI Wiki prefix sum and adjacent difference	`Reference`
USACO Guide more prefix sums	`Reference`
cppreference adjacent_difference	`Primary`

Source	Type
CSES Range Update Queries	`Practice`
CSES Problem Set	`Practice`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
D - Water Heater	`AtCoder`	`Medium`	Imos	-	-	Difference Array; Sweep Line; Events	A clean event-sweep difference-array problem.
Range Update Queries	`CSES`	`Medium`	Difference Array	Implementation-Heavy	Difference Arrays; Prefix Sums; Range Updates	Range-Add; Point-Query	The standard entry point for using a difference array to turn range updates into prefix scans.
D - Snuke Prime	`AtCoder`	`Hard`	Imos	-	-	Difference Array; Sweep Line; Interval-Cost	Sparse endpoints, then prefix accumulation.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Greg and Array	`Codeforces`	`Medium`	-	Modeling-Heavy; Implementation-Heavy	Difference Arrays; Prefix Sums; Offline Processing	Difference Array; Offline; Range-Operations	A strong benchmark for applying difference arrays both on operations and on the final array.
Little Girl and Maximum Sum	`Codeforces`	`Medium`	-	Greedy-Heavy; Math-Heavy	Difference Arrays; Sorting; Prefix Counts	Difference Array; Sorting; Frequency	A classic frequency-by-intervals problem where the difference array makes the key idea obvious.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`RANGEUPDATEQUERIES`	Range Update Queries	`primary`	`medium`	difference array updates; fenwick on diff; range add point query	Note	Code

python3 scripts/generate_problem_catalog.py