Data Structures -> Lazy Segment Tree¶

Deferred-tag segment tree for online range updates and range queries when a full segment can absorb the update in closed form.

Microtopics¶

Source	Type
SPOJ Classical	`Practice`
CSES Problem Set	`Practice`
AtCoder Library Practice Contest	`Practice`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
HORRIBLE	`SPOJ`	`Medium`	Range Queries, Lazy Propagation	Data-Structure-Heavy; Query-Heavy	Segment Tree Basics; Difference Arrays Contrast; Range Updates	Range-Add; Range-Sum; Classic	The cleanest exact range add + range sum benchmark for a first lazy segment tree.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Polynomial Queries	`CSES`	`Hard`	Range Queries	Data-Structure-Heavy; Math-Heavy	Lazy Propagation; Range Arithmetic; Tag Design	Lazy-Propagation; Range-Update; Arithmetic-Progression	A memorable benchmark where the update itself carries structure, not just one additive delta.
Range Updates and Sums	`CSES`	`Hard`	Range Queries	Data-Structure-Heavy	Lazy Propagation; Tag Composition; Range Assign	Lazy-Propagation; Range-Add; Range-Assign	The natural next benchmark once plain additive tags are stable and tag precedence becomes the real challenge.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Range Affine Range Sum	`AtCoder`	`Hard`	-	Data-Structure-Heavy; Verification	Lazy Propagation; Modular Arithmetic; Affine Tags	Lazy-Propagation; Affine-Update; Acl-Style	The cleanest external verifier once you want to think in generic lazy actions rather than one bespoke additive tag.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`HORRIBLEQUERIES`	Horrible Queries	`primary`	`medium`	lazy segment tree; range add range sum; deferred propagation	Note	Code

python3 scripts/generate_problem_catalog.py