Segment Trees and Lazy Propagation

Competitive-programming territory

Segment trees show up constantly in competitive programming and occasionally in “hard” interview problems (Range Sum Query, Count of Smaller Numbers After Self). They’re worth building real intuition for, even though most day-to-day backend code reaches for a database index instead.

A segment tree answers two questions fast, on the same array, at the same time: “what’s the sum/min/max over this range?” and “change this element (or this whole range).” Neither a plain array nor a simple prefix-sum array can do both cheaply — a segment tree can, in $O(\log n)$ per operation.

What you’ll learn

• Why prefix sums fall apart the moment the array needs to change, and what a segment tree trades in exchange for staying fast.
• Building an iterative, array-based segment tree that supports any associative merge (sum, min, max, …) with $O(\log n)$ point update and range query.
• Lazy propagation: how to push a range update through the tree in $O(\log n)$ instead of updating every affected leaf one at a time.
• The complexity trade-offs, and which LeetCode/CP problems reach for this structure.

Visual intuition

A range query does not walk to the leaves. Watch where it stops:

segtreeA query decomposes into O(log n) fully-covered nodesrange sum · O(log n)

1def build(a, node, lo, hi):2    if lo == hi:3        tree[node] = a[lo]                 # a leaf IS one element4        return5    mid = (lo + hi) // 26    build(a, 2*node,     lo,      mid)7    build(a, 2*node + 1, mid + 1, hi)8    tree[node] = tree[2*node] + tree[2*node + 1]9 10def query(node, lo, hi, l, r):11    if r < lo or hi < l:  return 0          # no overlap12    if l <= lo and hi <= r: return tree[node]   # FULLY inside — stop here13    mid = (lo + hi) // 214    return query(2*node, lo, mid, l, r) + query(2*node+1, mid+1, hi, l, r)

total24

builtEach node stores the sum of one range, shown beneath it. The root covers everything; leaves cover single elements. Building costs O(n) and every node's value is the sum of its two children — so an update touches only one root-to-leaf path.

Play‹›1/11⟲

Two rules do all the work: stop when a node lies entirely inside the query range, prune when it lies entirely outside. Everything between is split. A prefix-sum array answers the same query in O(1) but cannot survive updates, which is the trade-off segment trees exist to make.

The cue

You are looking at a segment tree when…

• The array is mutated between queries and each query is over a range — and the combining operation is min, max, gcd, or something else without an inverse. If it is a sum or an XOR, a Fenwick tree is a third of the code.
• You need range updates as well as range queries: “add 5 to everything in [l, r]”. That is lazy propagation, and no other structure on this course does it.
• Constraints are around $10^5$ elements with $10^5$ mixed operations — so $O(n)$ per query is too slow and $O(\log n)$ is expected.
• The problem is a sweep with a live “best in window” where the window’s contents change arbitrarily, not just at the ends. (If they only change at the ends, a monotonic deque is $O(n)$.)

The reframe: the tree is a set of precomputed answers for $O(n)$ canonical ranges, chosen so that any query range is the union of $O(\log n)$ of them and any element belongs to $O(\log n)$ of them. Query walks up combining the canonical pieces; update walks up recomputing the ones that contain the changed leaf.

Reach for something else when the array is static — a sparse table answers min/max in $O(1)$ per query, and a plain prefix-sum array does sums in $O(1)$; when the operation is invertible (Fenwick, less code, better constants); or when the range is the whole array every time (just keep a running value).

Why not just use a prefix-sum array?

A prefix-sum array answers “sum of [0, i)” in $O(1)$ — but the moment a single element changes, every prefix sum after it is stale, and fixing them all costs $O(n)$. A segment tree accepts a slightly slower query in exchange for a much faster update:

Approach	Range sum query	Point update	Range update
Plain array	$O(n)$ (walk the range)	$O(1)$	$O(n)$
Prefix-sum array	$O(1)$	$O(n)$ (rebuild suffix)	$O(n)$
Segment tree	$O(\log n)$	$O(\log n)$	$O(\log n)$ (with lazy propagation)

Whenever a problem needs both “query a range” and “update the array” — repeatedly, in any order — a segment tree (or its cousin, the Fenwick tree from the next lesson) is almost always the answer.

Building an iterative segment tree

Store the tree in one flat array of size 2n: leaves occupy indices n .. 2n - 1 (one per original element), and each internal node i merges its two children 2i and 2i + 1. Because the merge function is a parameter, the exact same class handles sum, min, max, gcd — anything associative:

segment_tree.py

class SegmentTree:
    def __init__(self, data, merge, identity):
        self.n = len(data)
        self.merge = merge
        self.identity = identity            # a value that doesn't affect merge, e.g. 0 for sum
        self.tree = [identity] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = data[i]  # leaves
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.merge(self.tree[2 * i], self.tree[2 * i + 1])
 
    def update(self, pos, value):
        """Point update: set data[pos] = value in O(log n)."""
        i = pos + self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.merge(self.tree[2 * i], self.tree[2 * i + 1])
 
    def query(self, left, right):
        """Range query over the half-open interval [left, right)."""
        result = self.identity
        left += self.n
        right += self.n
        while left < right:
            if left & 1:
                result = self.merge(result, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result = self.merge(result, self.tree[right])
            left //= 2
            right //= 2
        return result
 
 
data = [2, 4, 5, 7, 8, 9]
sum_tree = SegmentTree(data, merge=lambda a, b: a + b, identity=0)
print("sum[1:4):", sum_tree.query(1, 4))   # 4 + 5 + 7 = 16
 
sum_tree.update(2, 10)   # data[2] becomes 10
print("after point update, sum[1:4):", sum_tree.query(1, 4))   # 4 + 10 + 7 = 21
 
min_tree = SegmentTree(data, merge=min, identity=float("inf"))
print("min[1:4):", min_tree.query(1, 4))   # min(4, 5, 7) = 4

Both the left & 1 / right & 1 checks are the same trick: an odd left means the current node is a right child, so it’s outside its parent’s range and must be included directly before moving up; an odd right means the node just before it is a right child that needs including before shrinking the range. That’s the entire query logic — no recursion needed.

For a smaller, four-element example [2, 4, 5, 7], the recursive shape a segment tree conceptually represents looks like this (each node stores the sum of the range it covers):

diagram Segment tree over [2, 4, 5, 7]: every node stores the sum of its range mermaid

  graph TD
    N0["[0,3] sum=18"] --> N1["[0,1] sum=6"]
    N0 --> N2["[2,3] sum=12"]
    N1 --> N3["[0,0] sum=2"]
    N1 --> N4["[1,1] sum=4"]
    N2 --> N5["[2,2] sum=5"]
    N2 --> N6["[3,3] sum=7"]

A range query only ever visits $O(\log n)$ of these nodes: it descends until it finds a node fully inside the query range (use it whole, don’t descend further) or fully outside it (skip it entirely) — only nodes that are partially overlapped need to recurse into both children.

sketch Descending the tree for a range-sum query over [1, 3] p5.js Pause Restart

Yellow = partially overlapped (must recurse deeper); red = no overlap (skipped); green = fully covered (added as one unit, no further descent needed).

Lazy propagation: fast range updates

Point update handles “change one element.” But “add 5 to every element from index 3 to index 700” would need 698 point updates — $O(n \log n)$ total, too slow. Lazy propagation fixes this: when an update fully covers a node’s range, update that node’s stored value immediately, but only record the pending change in a lazy array instead of pushing it to the children right away. The children only find out about it the next time something actually needs to look inside them.

segment_tree_lazy.py

class LazySegmentTree:
    """Recursive segment tree: O(log n) range-add updates, O(log n) range-sum queries."""
 
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)   # sums
        self.lazy = [0] * (4 * self.n)   # pending range-add, not yet pushed to children
        self._build(data, 1, 0, self.n - 1)
 
    def _build(self, data, node, lo, hi):
        if lo == hi:
            self.tree[node] = data[lo]
            return
        mid = (lo + hi) // 2
        self._build(data, 2 * node, lo, mid)
        self._build(data, 2 * node + 1, mid + 1, hi)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
 
    def _push_down(self, node, lo, hi):
        if self.lazy[node] == 0:
            return
        mid = (lo + hi) // 2
        for child, child_lo, child_hi in (
            (2 * node, lo, mid),
            (2 * node + 1, mid + 1, hi),
        ):
            self.lazy[child] += self.lazy[node]
            self.tree[child] += self.lazy[node] * (child_hi - child_lo + 1)
        self.lazy[node] = 0
 
    def update_range(self, l, r, delta, node=1, lo=None, hi=None):
        """Add delta to every element in the inclusive range [l, r]."""
        if lo is None:
            lo, hi = 0, self.n - 1
        if r < lo or hi < l:
            return   # no overlap at all -- nothing to do
        if l <= lo and hi <= r:
            self.tree[node] += delta * (hi - lo + 1)   # fully covered: update now, defer children
            self.lazy[node] += delta
            return
        self._push_down(node, lo, hi)   # about to look inside -- children must be up to date
        mid = (lo + hi) // 2
        self.update_range(l, r, delta, 2 * node, lo, mid)
        self.update_range(l, r, delta, 2 * node + 1, mid + 1, hi)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
 
    def query_range(self, l, r, node=1, lo=None, hi=None):
        """Sum over the inclusive range [l, r]."""
        if lo is None:
            lo, hi = 0, self.n - 1
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.tree[node]
        self._push_down(node, lo, hi)
        mid = (lo + hi) // 2
        return (
            self.query_range(l, r, 2 * node, lo, mid)
            + self.query_range(l, r, 2 * node + 1, mid + 1, hi)
        )
 
 
data = [1, 3, 5, 7, 9, 11]
st = LazySegmentTree(data)
print("sum[1..4]:", st.query_range(1, 4))                    # 3+5+7+9 = 24
 
st.update_range(1, 3, 10)                                     # add 10 to indices 1..3
print("sum[1..4] after range add:", st.query_range(1, 4))    # (3+10)+(5+10)+(7+10)+9 = 54
print("sum[0..0] unaffected:", st.query_range(0, 0))          # still 1

The push_down rule, in one sentence

Whenever code is about to read or write inside a node’s children — never before — flush that node’s pending lazy value down first. Skip that rule and a node’s children silently disagree with what the node itself already claims.

Dry run

data = [2, 4, 5, 7, 8, 9], sum merge. With n = 6 the flat array holds 12 slots: leaves at indices 6–11, internal nodes at 1–5.

index	covers	value
6, 7, 8, 9, 10, 11	one element each	2, 4, 5, 7, 8, 9
3	leaves 6–7 → data[0..1]	6
4	leaves 8–9 → data[2..3]	12
5	leaves 10–11 → data[4..5]	17
2	nodes 4–5 → data[2..5]	29
1	nodes 2–3 → everything	35

Note the shape: node 3 sits at the same depth as nodes 4 and 5 but covers a different span. The 2n layout does not produce a neat perfect tree when n is not a power of two, and it does not need to — correctness only requires that node i is the merge of 2i and 2i+1.

Query [1, 5) — the sum of data[1..4] = 4 + 5 + 7 + 8 = 24. Pointers start at l = 1 + 6 = 7 and r = 5 + 6 = 11:

step	test	action	result	l, r after
1	l = 7 is odd	take leaf 7 (value 4), l += 1	4	8, 11
1	r = 11 is odd	r -= 1, take leaf 10 (value 8)	12	8, 10
—	climb	l //= 2, r //= 2	12	4, 5
2	l = 4 is even	nothing	12	4, 5
2	r = 5 is odd	r -= 1, take node 4 (value 12, covering data[2..3])	24	4, 4
—	climb; l == r → stop		24	2, 2

Three things this makes concrete:

• The query never descends. It starts at the leaves and climbs, absorbing whole nodes whenever the boundary is odd. Four elements were covered by three node reads — two leaves and one internal node — and on a large array that ratio is the $\log n$.
• “Odd index” means “this node is a right child, so its parent covers something outside the range”. That is the entire meaning of the & 1 tests; they are boundary handling, not bit trickery.
• The interval is half-open [l, r) and the code depends on it. l < r is the loop condition and r -= 1 before reading is what keeps the right end exclusive. Passing an inclusive range silently drops the last element — pass right + 1 or convert at the boundary, but pick one convention and keep it.

Complexity

Operation	Time	Space
Build	$O(n)$	$O(n)$
Point update	$O(\log n)$	—
Range query	$O(\log n)$	—
Range update (with lazy propagation)	$O(\log n)$	$O(n)$ extra for the lazy array
Range query (with pending lazy updates)	$O(\log n)$	—

Any associative merge works, but lazy propagation needs a matching “apply” rule

The plain segment tree above works unchanged for min, max, gcd, or any associative function — just swap merge. Lazy propagation is pickier: the pending update has to compose cleanly with the range size, which is why “add delta to a range” (multiply by range length) is the classic example. “Assign value to a range” also works with a small tweak; “multiply a range by k” needs two lazy arrays (one for add, one for multiply) tracked carefully together.

The variant map

Need	What changes	Note
Range sum, point update	merge = +, identity 0	a Fenwick tree is shorter — prefer it
Range min / max, point update	merge = min, identity inf	no Fenwick equivalent: min has no inverse
Range gcd, point update	merge = gcd, identity 0	any associative operation works unchanged
Range assign / add, range query	add a lazy[] array and push down before descending	the reason to choose a segment tree over everything else
Static array, range min	—	a sparse table is $O(1)$ per query
k-th element / order statistic	store subtree counts, descend by comparing them	$O(\log n)$, no binary search on top
Count / sum over a value range	index the tree by value, not position; coordinate-compress first	how inversion-counting problems map onto it
Merge sort tree	each node stores a sorted list of its range	$O(\log^2 n)$ queries, answers “how many < x in [l,r]”
2-D (grid ranges)	a segment tree of segment trees	$O(\log m \log n)$; usually the last resort
Persistent segment tree	copy the $O(\log n)$ nodes an update touches	query any historical version
LC 307 Range Sum Query — Mutable	the base case	Fenwick also solves it
LC 715 / 732 Range Module, Calendar III	range assign + count	lazy propagation, or an ordered interval map

Interview follow-ups

They ask	What they’re checking	The answer
“Segment tree or Fenwick?”	Judgement	Fenwick when the operation is invertible (sum, XOR) and updates are point updates — a third of the code and better constants. Segment tree the moment you need min/max/gcd, or range updates with lazy propagation
“Why is a query $O(\log n)$?”	The structure	Because the query range decomposes into at most two canonical nodes per level, and there are $\log n$ levels. The & 1 tests are what pick those nodes out at each boundary
“What does lazy propagation actually defer?”	The core idea	Applying a range update to every leaf. Instead you mark the node covering the range and push the mark down only when a later query needs to descend through it — so a range update stays $O(\log n)$ instead of $O(n)$
“When must you push down?”	The bug people hit	Before descending into children for either a query or an update. Forget it and children return values from before the pending update — a wrong answer with no crash
“Build it in $O(n)$”	Whether you know the iterative form	Fill the leaves at n..2n-1, then loop i from n-1 down to 1 computing tree[i] = merge(tree[2i], tree[2i+1]). Every child is already final when its parent is computed
“The array is static and queries are min”	Choosing the cheaper tool	Sparse table: $O(n\log n)$ preprocessing, $O(1)$ per query. A segment tree’s $O(\log n)$ is wasted when nothing ever changes
“Find the k-th smallest, with updates”	Extending it	Store a count per node and descend: at each node, if the left child’s count is ≥ k go left, else subtract and go right. $O(\log n)$, no binary search wrapper
“How big should the array be?”	The practical detail	2n for the iterative version; the recursive one is usually sized 4n because a non-power-of-two n can push nodes past 2n. Sizing it 2n recursively is a real out-of-range bug

Practice — real LeetCode problems

Three interval problems that a segment tree solves, with reference solutions that deliberately use the simplest structure that passes. That is the honest lesson: know when the heavy machinery earns its keep, and know what to reach for when it does not. Each editorial spells out the segment-tree version and when you would need it.

LC 732 — My Calendar III · Hard

Problem. Implement MyCalendarThree with book(startTime, endTime), which always succeeds and returns the largest k such that some point in time is covered by k bookings. Intervals are half-open [start, end).

Constraints. 0 <= start < end <= 10**9, at most 400 calls.

Examples. book(10,20) gives 1, book(50,60) gives 1, book(10,40) gives 2, book(5,15) gives 3, book(5,10) gives 3, book(25,55) gives 3

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Maximum interval overlap. The difference-array sweep is the idiomatic answer: +1 where an interval starts, -1 where it ends, and the running total at any point is the coverage there.

Time $O(n \log n)$ per book from the sort, so $O(n^2 \log n)$ overall. With at most 400 calls that is trivial. Space $O(n)$.

• Half-open intervals make the endpoints work. book(5,10) after book(10,20) returns 3, not 4: the -1 at 10 and the +1 at 10 cancel before the maximum is taken, because both land on the same key. If the intervals were closed you would need to order ends before starts explicitly.
• get(t, 0) + 1 rather than assignment, since several intervals can share an endpoint. Overwriting loses bookings.
• The answer never decreases across calls, so caching the running best and only re-sweeping is also valid — but the maximum must be recomputed, since a new interval can raise coverage anywhere.
• Return the maximum over the whole timeline, not the coverage of the interval just booked.

The segment tree version, and when you need it. Build a dynamic (implicit) segment tree over [0, 10**9) — creating child nodes only when touched — with lazy propagation for “add 1 to this range” and a stored maximum per node. Then book is $O(\log C)$ instead of $O(n \log n)$. That is the right structure if there were $10^5$ calls rather than 400. Coordinate compression is not available here because the calls arrive online, which is exactly the situation that forces a dynamic tree.

Follow-ups you should expect: “MyCalendar I (LC 729) — reject conflicts?” — keep sorted disjoint intervals and binary search; overlap means reject. “MyCalendar II (LC 731) — allow double booking but not triple?” — track the intervals booked once and the intersections booked twice. ”$10^5$ calls?” — the dynamic segment tree above. “Which time has the maximum?” — record the t where running hits best. “Report the total booked length?” — accumulate the covered spans during the same sweep.

LC 699 — Falling Squares · Hard

Problem. Squares drop one at a time; positions[i] = [left, sideLength] means a square occupying [left, left + sideLength) falls and rests on whatever is below. After each drop, report the tallest stack height so far.

Constraints. 1 <= len(positions) <= 1000, 1 <= left, sideLength <= 10**8.

Examples. [[1,2],[2,3],[6,1]] gives [2,5,5] · [[100,100],[200,100]] gives [100,100]

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

With len(positions) <= 1000, the $O(n^2)$ pairwise scan is $10^6$ comparisons and is the intended-to-pass solution. The interest is in the geometry and in what you would do if n were larger.

Time $O(n^2)$. Space $O(n)$.

• Strict overlap, not touching. [1,3) and [3,4) share only the point 3 and must not stack. l < right and left < r encodes that. Using <= instead still returns [2,5,5] on the first example — so that one will not save you — but turns [[100,100],[200,100]] into [100,200], wrongly stacking two squares that merely touch at 200. [[1,2],[3,2]] is the same trap in miniature: [2,2] strictly, [2,4] loosely. This is the bug to look for first.
• The output is a running maximum. [[100,100],[200,100]] gives [100,100] — the second square is disjoint and only 100 tall, but the answer never goes down.
• The base is 0 when nothing overlaps, so a square landing on empty ground has top equal to its side.
• Coordinates reach $10^8$, so no array can be indexed by position. Anything faster must compress coordinates first.

The segment tree version. Coordinate-compress all left and left + side values into at most 2n boundaries, then use a segment tree over those cells supporting range max query and range assign (lazy propagation, since a landing square sets a uniform new height over its span). Each drop is $O(\log n)$, giving $O(n \log n)$ overall — the answer to “what if n were $10^5$?”. Range assign rather than range add is the detail to get right, and it is a genuinely good exercise in lazy propagation.

Follow-ups you should expect: ”$n = 10^5$?” — the compressed segment tree above. “Squares of different widths that can tip over?” — no longer a clean interval problem. “Report the final skyline?” — LC 218, a different sweep with a heap. “Rectangle Area II (LC 850)?” — the same compress-then-segment-tree technique, measuring covered length instead of height. “Why not a heap?” — a heap orders by height but cannot answer “which of these overlap me”.

LC 715 — Range Module · Hard

Problem. Track ranges of numbers as half-open intervals. addRange(left, right) adds every number in [left, right), queryRange(left, right) returns whether every number in [left, right) is currently tracked, and removeRange(left, right) stops tracking every number in it.

Constraints. 1 <= left < right <= 10**9, at most 10**4 calls.

Examples. addRange(10,20), removeRange(14,16), then queryRange(10,14) gives True, queryRange(13,15) gives False, queryRange(16,17) gives True

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The structure is a sorted list of disjoint half-open intervals, and the invariant — always disjoint, always sorted, never touching — is what keeps every operation to a couple of bisect calls plus a slice assignment.

Getting the four search bounds right is the entire problem:

Operation	Bounds	Why
addRange	bisect_left(ends, left) .. bisect_right(starts, right)	touching counts, so merge adjacent intervals too
queryRange	bisect_right(starts, left) - 1	the only interval that can contain left
removeRange	bisect_right(ends, left) .. bisect_left(starts, right)	touching does not count, so leave neighbours alone

The asymmetry is deliberate: for addRange, [1,5) and [5,9) should merge into [1,9), so the bound is inclusive of touching. For removeRange, removing [5,9) must not disturb an interval ending exactly at 5. Mixing these up is the single most common failure, and the sixth call in the test — removeRange(0,100) wiping everything — checks the wide case.

Time $O(\log n)$ to locate, plus $O(n)$ worst case for the slice assignment, which is fine at $10^4$ calls. Space $O(n)$ in the number of disjoint intervals.

• ends[i] >= right for the query, because the intervals are half-open: [10,20) fully covers [10,20).
• Slice assignment replaces a whole run in one statement, which is what keeps the merge readable. Doing it with pop in a loop is where off-by-one bugs breed.
• A removal can split one interval into two — both fragments, one, or neither may survive. Building the survivors into a small list handles all four cases uniformly.
• Adding an already-covered range is a no-op in effect: the merge produces the same interval back.

The segment tree version. A dynamic segment tree over [1, 10**9) with lazy range assign of 0 or 1 and a stored “is this whole node covered” flag gives $O(\log C)$ per operation with no slice cost. That is the textbook answer and the right one if the coordinates were dense or the calls numbered $10^6$. At $10^4$ calls the interval list is simpler and faster in practice — and being able to say why you chose it is the point.

Follow-ups you should expect: “Count the tracked numbers?” — maintain a running total of interval lengths as you add and remove. “The largest tracked gap?” — a heap over gaps, or scan the list. ”$10^6$ calls?” — the dynamic segment tree. “Query whether any number in the range is tracked, rather than all?” — test for overlap instead of containment, which is a different bound again. “Why half-open?” — it makes adjacency and merging arithmetic instead of case analysis.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

5 problems

0 easy2 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○307Range Sum Query - MutablemediumThe textbook use case: point updates interleaved with range-sum queries
• ○308Range Sum Query 2D - MutablepremiummediumThe same idea nested two levels deep (a segment tree of segment trees, or a 2D Fenwick tree from the next lesson)
• ○315Count of Smaller Numbers After SelfhardA segment tree (or Fenwick tree) over compressed values, counting how many smaller elements have been seen so far while scanning right to left
• ○699Falling SquareshardRange-max query to find the landing height, then a range "set to a new height" update -- lazy propagation on a max segment tree over compressed coordinates
• ○732My Calendar IIIhardRange-add "how many bookings overlap here" is lazy-propagation range update plus a range-max query

Self-check

pch.quizTag Segment trees — self-check

1. When is a segment tree the right choice over a Fenwick tree?

   A Always — it is strictly more general B When the operation has no inverse (min, max, gcd) or when you need RANGE updates with lazy propagation; for invertible operations with point updates, Fenwick is a third of the code C When n exceeds 10^5 D When the array is static
   pch.quizShowAnswer

   B — When the operation has no inverse (min, max, gcd) or when you need RANGE updates with lazy propagation; for invertible operations with point updates, Fenwick is a third of the code — Fenwick's range query is prefix(r) − prefix(l−1), which requires subtraction. Min has no inverse, so there is no Fenwick equivalent — that is the dividing line.

2. In the iterative query, what do the `l & 1` and `r & 1` tests mean?

   A They check whether the range length is even B They detect that the boundary node is a RIGHT child, so its parent covers something outside the query — that node must be absorbed now rather than by the parent C They are a fast modulo for the tree depth D They pick between min and max
   pch.quizShowAnswer

   B — They detect that the boundary node is a RIGHT child, so its parent covers something outside the query — that node must be absorbed now rather than by the parent — It is boundary handling, not bit trickery. In the dry run, query [1,5) absorbs two leaves and one internal node — three reads for four elements, and that ratio is the log n.

3. What does lazy propagation defer, and when must the deferred work happen?

   A It defers the query until an update arrives B It defers applying a range update to the leaves: mark the covering node, and push the mark down only when a later operation needs to descend through it C It defers the build until the first query D It defers merging children
   pch.quizShowAnswer

   B — It defers applying a range update to the leaves: mark the covering node, and push the mark down only when a later operation needs to descend through it — Forgetting to push down before descending is the classic bug: children return values from before the pending update, so the answer is wrong with no crash.

4. The array is static and every query is a range minimum. Segment tree?

   A Yes, it is the standard tool B No — a sparse table preprocesses in O(n log n) and answers in O(1). The segment tree's O(log n) per query buys mutability you are not using C Yes, but only for n > 1000 D No, use a Fenwick tree
   pch.quizShowAnswer

   B — No — a sparse table preprocesses in O(n log n) and answers in O(1). The segment tree's O(log n) per query buys mutability you are not using — Matching the structure to whether the data changes is the recurring decision across this phase: static → sparse table, point updates + invertible → Fenwick, everything else → segment tree.

5. Why is the recursive implementation usually sized 4n rather than 2n?

   A To leave room for lazy tags B Because when n is not a power of two, recursive node indices can exceed 2n — the iterative bottom-up layout fits in 2n, the recursive one does not C Because each node stores two values D It is superstition; 2n is always enough
   pch.quizShowAnswer

   B — Because when n is not a power of two, recursive node indices can exceed 2n — the iterative bottom-up layout fits in 2n, the recursive one does not — Sizing the recursive version 2n is a genuine out-of-range bug that only appears for certain n. The iterative form in this page's template is safe at 2n.

6. How would you find the k-th smallest element with updates allowed?

   A Sort after every update B Store a count per node and descend: if the left child's count is ≥ k go left, otherwise subtract it and go right — O(log n) with no binary search wrapper C Binary search the value range, querying the count each time D Use a heap
   pch.quizShowAnswer

   B — Store a count per node and descend: if the left child's count is ≥ k go left, otherwise subtract it and go right — O(log n) with no binary search wrapper — Binary search plus counting also works at O(log² n). Descending directly is the better answer, and it is the same idea as the order-statistic augmentation on a BST.

Recall card

• Cue — range queries on a mutating array where the operation has no inverse (min, max, gcd), or where updates apply to a whole range.
• Layout — flat array of 2n: leaves at n..2n-1, node i = merge(2i, 2i+1). Build bottom-up in $O(n)$.
• Query [l, r) — half-open. Start at l+n, r+n; absorb the node when the index is odd, then climb. $O(\log n)$.
• Update — write the leaf, then walk to the root re-merging. $O(\log n)$.
• Lazy propagation — mark the covering node, push down before descending. That push is what people forget, and it fails silently.
• Sizing — 2n iterative, 4n recursive.
• Choose the tool — static + min/max → sparse table ($O(1)$ query); invertible + point updates → Fenwick; otherwise this.
• Augmentations — subtree counts give $O(\log n)$ k-th element; a sorted list per node gives the merge sort tree.

Recap

• Prefix sums are $O(1)$ to query but $O(n)$ to update; a segment tree trades a little query speed for $O(\log n)$ updates too.
• The iterative, array-based segment tree stores leaves at n .. 2n-1 and supports point update + range query in $O(\log n)$ for any associative merge function.
• Lazy propagation upgrades point updates to range updates, still $O(\log n)$, by deferring the push to children until something actually needs to look inside them.
• A range query only ever visits $O(\log n)$ nodes: skip fully-outside nodes, use fully-inside nodes whole, recurse only into partial overlaps.

Next: Fenwick Tree (Binary Indexed Tree) — a much shorter, non-recursive structure that handles the same range-sum-and-point-update problem with roughly a third of the code, once the operation is invertible.