Segment trees

Problem

Prefix sums answer any range sum in O(1), but only on an array that never changes: one update shifts every prefix after it, costing O(n). Recomputing each query from the raw array is the opposite trade, O(1) to update and O(n) to ask. When a problem interleaves the two, up to 10⁵ of each, both are quadratic. A segment tree meets in the middle at O(log n) for each, and it works for any operation that combines two neighbouring answers into one, such as sum, min, max, gcd or "count of values in a bucket".

Intuition

Imagine a tournament bracket over the array. Each leaf is one element. Each match above combines two neighbours into one result, so the node above leaves 2 and 3 holds their sum, the node above that holds the sum of 0 to 3, and the root holds everything. Every node is responsible for one contiguous block, and the blocks at each level tile the array without overlap.

To answer a range, walk down from the root. A block entirely inside the range is used whole, without looking inside it. A block entirely outside is ignored. Only a block that straddles one of the range's two ends needs opening, and since a range has only two ends, only two blocks per level can straddle. That is why a query touches a few nodes per level and never the whole array. To change an element, fix its leaf and then recompute every ancestor on the way up: one node per level.

Amber nodes straddle an end of the range and are opened; green nodes lie inside it and are used whole; red outlines are visited and rejected at once; plain nodes are never touched. The diagram scrolls sideways on a narrow screen.

Mechanics

Layout

Store the tree in a flat list, the way a heap is stored. Node 1 is the root and covers [0, n - 1]. Node v covering [lo, hi] has children 2v and 2v + 1 covering [lo, mid] and [mid + 1, hi] with mid = (lo + hi) // 2. A node whose range is one element is a leaf. Building is a post-order recursion: build both children, then set the node to their combination, which visits each of the 2n − 1 nodes once.

The invariant

Every node holds the combination of the array values in its range. Build establishes it bottom-up. A point update breaks it only at the nodes whose range contains the changed index, which are exactly the leaf and its ancestors, and recomputing them bottom-up restores it, since each depends only on its two children. The combining operation must be associative, so that splitting a range into pieces and combining the pieces gives the same answer in any grouping; it does not have to be commutative if pieces are combined left to right, and it needs an identity (0 for sum, infinity for min) to return for an empty piece.

The query

query(node) for a target range [left, right] has three cases. If the node's range is disjoint from the target, return the identity. If it is contained in the target, return the stored value: by the invariant it is exactly that block's answer. Otherwise it overlaps partly, so recurse into both children and combine. Correctness follows by induction on the node's size: the inside and outside cases are right by the invariant, and a partial node's range is the disjoint union of its children's, so combining their correct answers for the overlap is correct.

Why O(log n)

At any level, the nodes that partly overlap the target are the at most two that contain left or right without lying inside the range. Any node strictly between them lies inside, and the recursion never descends below an inside or outside node. So each level has at most two split nodes, they open at most four children on the next level, and the depth is ⌈log₂ n⌉. A query therefore visits at most about 4 log₂ n nodes. The table in the tradeoffs section checks that bound against every possible range.

Worked example

The tree over [5, 8, 6, 3, 2, 7, 2, 6]. Node values by level, root first:

Query the sum of indices 2 to 6. The visits in order, matching the first diagram:

The answer is 20, assembled from 3 stored values after 9 visits. The same ranges with min as the combining operation give 2.

Set index 3 to 10. Only the leaf and its ancestors change:

4 of 15 nodes change; the array is now [5, 8, 6, 10, 2, 7, 2, 6] and the root holds 46.

Amber nodes are recomputed from their children after the leaf changes, bottom to top.

Implementation

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self._build(1, 0, self.n - 1, nums)

    def _build(self, node, lo, hi, nums):
        if lo == hi:
            self.tree[node] = nums[lo]
            return
        mid = (lo + hi) // 2
        self._build(2 * node, lo, mid, nums)
        self._build(2 * node + 1, mid + 1, hi, nums)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, index, value, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if lo == hi:
            self.tree[node] = value
            return
        mid = (lo + hi) // 2
        if index <= mid:
            self.update(index, value, 2 * node, lo, mid)
        else:
            self.update(index, value, 2 * node + 1, mid + 1, hi)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, left, right, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if right < lo or hi < left:
            return 0
        if left <= lo and hi <= right:
            return self.tree[node]
        mid = (lo + hi) // 2
        return (self.query(left, right, 2 * node, lo, mid)
                + self.query(left, right, 2 * node + 1, mid + 1, hi))

For min or max, replace the + in all three places and return the identity (math.inf for min) from the disjoint case.

Variations and edge cases

Bottom-up, in 2n slots. Put the leaves at tree[n:] and fill parents from the back. A query climbs from both ends at once, taking a node whenever the boundary is a right child on the left side or a left child on the right side. No recursion and half the memory:

class BottomUpTree:
    def __init__(self, nums):
        self.n = n = len(nums)
        self.tree = [0] * n + list(nums)
        for i in range(n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        i = index + self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left, right):
        total, lo, hi = 0, left + self.n, right + self.n + 1
        while lo < hi:
            if lo & 1:
                total += self.tree[lo]
                lo += 1
            if hi & 1:
                hi -= 1
                total += self.tree[hi]
            lo //= 2
            hi //= 2
        return total

Lazy propagation for range updates. Adding v to every element of a range would touch up to n leaves. Instead, a node fully inside the update adds v × length to its own total and remembers v as pending; the pending value is pushed to its children only when a later call needs to look below it:

class LazyTree:
    def __init__(self, n):
        self.n = n
        self.total = [0] * (4 * n)
        self.pending = [0] * (4 * n)

    def _apply(self, node, lo, hi, delta):
        self.total[node] += delta * (hi - lo + 1)
        self.pending[node] += delta

    def _push(self, node, lo, mid, hi):
        if self.pending[node]:
            self._apply(2 * node, lo, mid, self.pending[node])
            self._apply(2 * node + 1, mid + 1, hi, self.pending[node])
            self.pending[node] = 0

    def add(self, left, right, delta, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if right < lo or hi < left:
            return
        if left <= lo and hi <= right:
            self._apply(node, lo, hi, delta)
            return
        mid = (lo + hi) // 2
        self._push(node, lo, mid, hi)
        self.add(left, right, delta, 2 * node, lo, mid)
        self.add(left, right, delta, 2 * node + 1, mid + 1, hi)
        self.total[node] = self.total[2 * node] + self.total[2 * node + 1]

    def query(self, left, right, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if right < lo or hi < left:
            return 0
        if left <= lo and hi <= right:
            return self.total[node]
        mid = (lo + hi) // 2
        self._push(node, lo, mid, hi)
        return (self.query(left, right, 2 * node, lo, mid)
                + self.query(left, right, 2 * node + 1, mid + 1, hi))

Over values instead of positions. To count, for each element, how many smaller values come after it, compress the values to ranks 0 to k − 1, walk the array from the right, query the sum of ranks below the current one, then add 1 at its rank. The same trick, with max instead of sum, gives the longest increasing subsequence ending at each value.

• Array size. With the recursive layout, node indices can exceed 2n when n is not a power of two; 4n is always enough. The table below shows the largest index actually used.
• Inclusive or half-open. Pick [left, right] or [left, right) once and use it in every comparison; mixing them drops or double-counts a boundary element.
• Empty array. _build(1, 0, -1) never reaches a leaf and recurses until the stack overflows; guard n == 0 first.
• Recursion depth. The depth is only about log₂ n, so Python's recursion limit is not a problem here, unlike a DFS on a path-shaped graph.

Complexity and tradeoffs

Build is O(n) time and the tree uses O(n) space; a query or a point update is O(log n); a lazy range update is O(log n) as well. The query bound, checked by running every possible range:

• Brute-force baseline. With q queries and u updates, a plain array costs O(u + qn), prefix sums O(un + q), and a segment tree O((u + q) log n).
• Against a Fenwick tree. A Fenwick (binary indexed) tree does prefix sums with point updates in fewer lines and less memory, but it needs an invertible operation to turn prefixes into ranges, so it cannot do range min or max directly. The segment tree is the general tool; the Fenwick tree is the compact special case.
• Against a sorted container. "How many values below x" can also be answered by binary search over a sorted list, but inserting into a Python list is O(n). A segment tree over ranks keeps every operation at O(log n), at the cost of knowing all values up front for compression.
• When it is overkill. If updates never happen, use prefix sums or a sparse table. If the queries are a sliding window, a monotonic deque gives O(1) amortized. In an interview, say that the tree exists and why before writing 40 lines of it.

Problems

No problem on the four lists has this page as its home, which is why it sits under Beyond the interview.

For practice beyond the lists, in rising difficulty:

• 307. Range Sum Query - Mutable Medium
  The template on this page, unchanged: point updates and range sums interleaved.
• 315. Count of Smaller Numbers After Self Hard
  Index the tree by value rank and sweep from the right, asking how many smaller ranks are already present.
• 699. Falling Squares Hard
  Each square reads the max height over its footprint and then raises that whole footprint: a range max query followed by a range assignment.
• 2407. Longest Increasing Subsequence II Hard
  The best chain ending at value v extends the best chain among values in [v − k, v − 1], a range max over values.

Connections

A segment tree is prefix sums made dynamic, built by the divide-and-conquer recursion of merge sort, and stored with the index arithmetic of a heap. Over value ranks it answers the questions a balanced BST with subtree sizes would, and over coordinates it turns a sweep line into an online structure. Range max over values speeds up LIS-style DPs whose transition looks back over a band of values.

Check yourself

References

• Bentley, J. L., "Solutions to Klee's rectangle problems", unpublished manuscript, Carnegie Mellon University, 1977: the origin of the segment tree.
• de Berg, Cheong, van Kreveld and Overmars, Computational Geometry: Algorithms and Applications, 3rd edition, chapter 10, section 10.3 "Segment Trees".
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, chapter 14, "Augmenting Data Structures", for the idea of storing a subtree's summary at each node.
• Sedgewick and Wayne, Algorithms, 4th edition, section 2.4, for the implicit array layout with children at 2k and 2k + 1.
• Skiena, S., The Algorithm Design Manual, the catalog entry "Range Search", on choosing among range-query structures.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.