Segment trees, Fenwick trees, and tree DP for range queries and complex tree problems.
Advanced tree structures support efficient range queries and updates. Segment trees answer range queries in O(log n) and support point/range updates. Fenwick trees (BIT) are simpler for prefix sum queries. These appear in hard interview questions and competitive programming.
Segment/Fenwick O(log n) per query/update
O(n)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
build O(n), range query O(log n), point update O(log n)
defer range updates for O(log n) range update too
prefix sum in O(log n); simpler than segment tree
O(n log n) build, O(1) range min/max query; immutable
define dp on tree nodes, combine from children up
compute dp for each node as root in O(n)