Skip to content
Python Central Hub

Segment Trees and Lazy Propagation

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)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 (sumsum, minmin, maxmax, …) with O(log⁡n)O(\log n) point update and range query.
  • Lazy propagation: how to push a range update through the tree in O(log⁡n)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.

Why not just use a prefix-sum array?

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

ApproachRange sum queryPoint updateRange update
Plain arrayO(n)O(n) (walk the range)O(1)O(1)O(n)O(n)
Prefix-sum arrayO(1)O(1)O(n)O(n) (rebuild suffix)O(n)O(n)
Segment treeO(log⁡n)O(\log n)O(log⁡n)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 2n2n: leaves occupy indices n .. 2n - 1n .. 2n - 1 (one per original element), and each internal node ii merges its two children 2i2i and 2i + 12i + 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
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 & 1left & 1 / right & 1right & 1 checks are the same trick: an odd leftleft 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 rightright 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][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

A range query only ever visits O(log⁡n)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
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(nlog⁡n)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 lazylazy 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
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

Complexity

OperationTimeSpace
BuildO(n)O(n)O(n)O(n)
Point updateO(log⁡n)O(\log n)—
Range queryO(log⁡n)O(\log n)—
Range update (with lazy propagation)O(log⁡n)O(\log n)O(n)O(n) extra for the lazylazy array
Range query (with pending lazy updates)O(log⁡n)O(\log n)—

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 MyCalendarThreeMyCalendarThree with book(startTime, endTime)book(startTime, endTime), which always succeeds and returns the largest kk such that some point in time is covered by kk bookings. Intervals are half-open [start, end)[start, end).

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

Examples. book(10,20)book(10,20) gives 11, book(50,60)book(50,60) gives 11, book(10,40)book(10,40) gives 22, book(5,15)book(5,15) gives 33, book(5,10)book(5,10) gives 33, book(25,55)book(25,55) gives 33

Editorial · approach, complexity, follow-ups

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

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

  • Half-open intervals make the endpoints work. book(5,10)book(5,10) after book(10,20)book(10,20) returns 3, not 4: the -1-1 at 10 and the +1+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) + 1get(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)[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 bookbook is O(log⁡C)O(\log C) instead of O(nlog⁡n)O(n \log n). That is the right structure if there were 10510^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. ”10510^5 calls?” — the dynamic segment tree above. “Which time has the maximum?” — record the tt where runningrunning hits bestbest. “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]positions[i] = [left, sideLength] means a square occupying [left, left + sideLength)[left, left + sideLength) falls and rests on whatever is below. After each drop, report the tallest stack height so far.

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

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

Editorial · approach, complexity, follow-ups

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

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

  • Strict overlap, not touching. [1,3)[1,3) and [3,4)[3,4) share only the point 3 and must not stack. l < right and left < rl < right and left < r encodes that. Using <=<= instead still returns [2,5,5][2,5,5] on the first example — so that one will not save you — but turns [[100,100],[200,100]][[100,100],[200,100]] into [100,200][100,200], wrongly stacking two squares that merely touch at 200. [[1,2],[3,2]][[1,2],[3,2]] is the same trap in miniature: [2,2][2,2] strictly, [2,4][2,4] loosely. This is the bug to look for first.
  • The output is a running maximum. [[100,100],[200,100]][[100,100],[200,100]] gives [100,100][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 10810^8, so no array can be indexed by position. Anything faster must compress coordinates first.

The segment tree version. Coordinate-compress all leftleft and left + sideleft + side values into at most 2n2n 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)O(\log n), giving O(nlog⁡n)O(n \log n) overall — the answer to “what if nn were 10510^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=105n = 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)addRange(left, right) adds every number in [left, right)[left, right), queryRange(left, right)queryRange(left, right) returns whether every number in [left, right)[left, right) is currently tracked, and removeRange(left, right)removeRange(left, right) stops tracking every number in it.

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

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

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 bisectbisect calls plus a slice assignment.

Getting the four search bounds right is the entire problem:

OperationBoundsWhy
addRangeaddRangebisect_left(ends, left)bisect_left(ends, left) .. bisect_right(starts, right)bisect_right(starts, right)touching counts, so merge adjacent intervals too
queryRangequeryRangebisect_right(starts, left) - 1bisect_right(starts, left) - 1the only interval that can contain leftleft
removeRangeremoveRangebisect_right(ends, left)bisect_right(ends, left) .. bisect_left(starts, right)bisect_left(starts, right)touching does not count, so leave neighbours alone

The asymmetry is deliberate: for addRangeaddRange, [1,5)[1,5) and [5,9)[5,9) should merge into [1,9)[1,9), so the bound is inclusive of touching. For removeRangeremoveRange, removing [5,9)[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)removeRange(0,100) wiping everything — checks the wide case.

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

  • ends[i] >= rightends[i] >= right for the query, because the intervals are half-open: [10,20)[10,20) fully covers [10,20)[10,20).
  • Slice assignment replaces a whole run in one statement, which is what keeps the merge readable. Doing it with poppop 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)[1, 10**9) with lazy range assign of 0 or 1 and a stored “is this whole node covered” flag gives O(log⁡C)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 10610^6. At 10410^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. ”10610^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

#ProblemDifficultyThe twist
307Range Sum Query - MutableMediumThe textbook use case: point updates interleaved with range-sum queries
308Range Sum Query 2D - MutableMedium · PremiumThe 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
732My Calendar IIIHardRange-add “how many bookings overlap here” is lazy-propagation range update plus a range-max query
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

Recap

  • Prefix sums are O(1)O(1) to query but O(n)O(n) to update; a segment tree trades a little query speed for O(log⁡n)O(\log n) updates too.
  • The iterative, array-based segment tree stores leaves at n .. 2n-1n .. 2n-1 and supports point update + range query in O(log⁡n)O(\log n) for any associative merge function.
  • Lazy propagation upgrades point updates to range updates, still O(log⁡n)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)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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Was this page helpful?

Let us know how we did