Segment Tree and Fenwick Tree

Advanced range-query structures. A Fenwick tree (BIT) handles point-update plus prefix-sum query in O(log n); a segment tree generalizes to range min/max/sum/gcd, with lazy propagation for range updates. Not asked in most standard interviews, but shows up in a handful of hard LeetCode range-query problems and in competitive programming.

Sub-patterns

• A — Fenwick Tree. Point update, prefix-sum query, O(log n).
• B — Segment Tree. Range sum/min/max/gcd queries.
• C — Lazy Propagation. Deferring range updates until a query actually needs that subtree.

Practice set (4)

• Medium — Range Sum Query - Mutable
• Hard — Count of Range Sum, The Skyline Problem, Falling Squares