Data Structures -> Segment Tree

General range query/update structure built on monoids and lazy propagation, with tree walking for advanced queries.

• Topic slug: data-structures/segment-tree
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 4
• Repo companion pages: 0
• Curated external problems: 8

Microtopics

• monoid
• build
• point-update
• range-query
• lazy-propagation
• tree-walking
• max_right

Learning Sources

Source	Type
AtCoder ACL Segtree	Primary
cp-algorithms segment tree	Reference
OI Wiki segment tree	Reference

Practice Sources

Source	Type
AtCoder Library Practice Contest	Practice
CSES Problem Set	Practice

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Dynamic Range Minimum Queries	CSES	Medium	-	Data-Structure-Heavy	Segment Tree Basics; Min Monoid; Updates	Range-Min; Point-Update	A direct min-query counterpart to the range-sum baseline.
Dynamic Range Sum Queries	CSES	Medium	-	Data-Structure-Heavy; Query-Heavy	Segment Tree Basics; Range Aggregation; Updates	Point-Update; Range-Sum	A standard point-update/range-query baseline for segment trees.

Classics

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Hotel Queries	CSES	Medium	-	Data-Structure-Heavy; Greedy-Heavy	Segment Tree; Binary Search On Tree; Greedy Assignment	First-Fit; Prefix-Max; Max-Query	A classic first-position query problem that is very segment-tree friendly.
Prefix Sum Queries	CSES	Hard	-	Query-Heavy; Data-Structure-Heavy	Segment Trees; Prefix Sums; Max-Prefix Maintenance	Prefix-Max; Range-Query	A strong benchmark for maintaining multiple aggregate values per segment.

Advanced

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Point Set Range Composite	Library Checker	Hard	-	Query-Heavy; Data-Structure-Heavy	Segment Tree; Monoids; Function Composition	Function-Composition	A strong official benchmark for monoid segment trees beyond numeric aggregates.
Polynomial Queries	CSES	Hard	-	Data-Structure-Heavy; Math-Heavy	Lazy Propagation; Segment Trees; Range Arithmetic	Lazy-Propagation; Range-Add; Arithmetic-Progression; Range-Update	A memorable advanced benchmark for non-uniform range updates and sum queries.
Range Updates and Sums	CSES	Hard	-	Data-Structure-Heavy	Lazy Propagation; Segment Tree Merges; Range Updates	Lazy-Propagation; Range-Add; Range-Assign	A high-value lazy-propagation benchmark with both add and assign operations.
Subarray Sum Queries	CSES	Hard	-	Data-Structure-Heavy; Query-Heavy	Segment Trees; Kadane-Style Merging; Point Updates	Max-Subarray; Point-Update	A classic advanced segment-tree problem for storing subarray summary states.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
DYNAMICRANGESUMQUERIES	Dynamic Range Sum Queries	primary	medium	iterative segment tree; point assignment; range sum query	Note	Code
PATHQUERIES2	Path Queries II	secondary	medium	heavy light decomposition; path query decomposition; segment tree on base array	Note	Code
RANGEQUERIESANDCOPIES	Range Queries and Copies	secondary	hard	persistent segment tree; path copying; versioned range sum	Note	Code
VMWTREE	Lại là cây khung	secondary	hard	path reverse; path sequence queries; heavy-light decomposition	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py