Segment Tree: Range Queries and Updates

A segment tree is a balanced binary tree that stores aggregate information about contiguous ranges of an array. It supports range queries, such as range sum or range minimum, and point or range updates, all in O(log n) time. When a problem screams “I need to repeatedly ask about a sub-array and also change values,” a segment tree is usually the answer.

The Shape of the Tree

Imagine an array of size n. The segment tree has roughly 2n leaves and 4n total nodes if you allocate it as a flat array. The root represents the full range, each internal node represents a contiguous subrange, and the two children split that subrange in half. Leaves represent single elements.

For an array of size 8, the root covers indices 0 to 7, its children cover 0 to 3 and 4 to 7, their children cover 0 to 1, 2 to 3, 4 to 5, 6 to 7, and the leaves cover single indices. Each level of the tree halves the range.

Recursive Implementation

A clean recursive implementation uses three core operations: build, update, and query. We store the tree in a flat list of size 4 times n, which is enough for any n.

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

    def _build(self, data, node, l, r):
        if l == r:
            self.tree[node] = data[l]
            return
        m = (l + r) // 2
        self._build(data, 2 * node, l, m)
        self._build(data, 2 * node + 1, m + 1, r)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, idx, value):
        self._update(1, 0, self.n - 1, idx, value)

    def _update(self, node, l, r, idx, value):
        if l == r:
            self.tree[node] = value
            return
        m = (l + r) // 2
        if idx <= m:
            self._update(2 * node, l, m, idx, value)
        else:
            self._update(2 * node + 1, m + 1, r, idx, value)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, ql, qr):
        return self._query(1, 0, self.n - 1, ql, qr)

    def _query(self, node, l, r, ql, qr):
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        m = (l + r) // 2
        return self._query(2 * node, l, m, ql, qr) + self._query(2 * node + 1, m + 1, r, ql, qr)

st = SegTree([1, 3, 5, 7, 9, 11])
print(st.query(1, 3))
st.update(2, 10)
print(st.query(1, 3))

Each query visits O(log n) nodes because the range either fully contains the current segment, lies fully outside it, or splits at the midpoint with bounded total descent.

Iterative Implementation

For competitive programming, an iterative version is often preferred because it is shorter, faster, and free of recursion overhead. It uses the standard “leaves at positions n through 2n minus 1” layout.

class IterSegTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        for i, x in enumerate(data):
            self.tree[self.n + i] = x
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

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

    def query(self, l, r):
        res = 0
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                res += self.tree[r]
            l //= 2
            r //= 2
        return res

This implementation handles half-open ranges. Both versions support O(log n) updates and queries with O(n) build time.

Changing the Aggregate

The same structure handles minimum, maximum, GCD, XOR, or any associative operation. Replace the plus operator with the operation of interest, and use the operation’s identity element instead of zero for empty ranges. For minimum, the identity is positive infinity. For maximum, it is negative infinity. For XOR, it is zero.

Lazy Propagation

Vanilla segment trees handle point updates well, but range updates, like “add 5 to every element in range l to r,” would naively cost O(n log n). Lazy propagation fixes that by deferring updates. Each node carries a pending update tag that is applied when the node is queried or when its children must be touched.

class LazySegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def _push(self, node, l, r):
        if self.lazy[node]:
            self.tree[node] += (r - l + 1) * self.lazy[node]
            if l != r:
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, ql, qr, value, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        self._push(node, l, r)
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.lazy[node] += value
            self._push(node, l, r)
            return
        m = (l + r) // 2
        self.update(ql, qr, value, 2 * node, l, m)
        self.update(ql, qr, value, 2 * node + 1, m + 1, r)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Lazy propagation keeps both range updates and range queries at O(log n).

Segment Tree Versus Fenwick Tree

If you only need prefix sums with point updates, a Fenwick tree, also called a binary indexed tree, is shorter and faster by a constant factor. Segment trees are more general: they handle min, max, GCD, and arbitrary aggregates, as well as range updates with lazy propagation.

Rule of thumb: reach for Fenwick when the problem is “prefix sum plus point update” and reach for segment tree the moment you need anything else.

Common Use Cases

Range sum queries on a mutable array. Range minimum queries for sliding window analysis or histograms. Order statistics with updates, by storing counts of values in each bucket. 2D segment trees for problems on a grid. Persistent segment trees for queries on historical versions of an array.

For broader context on time complexity, see /blog/big-o-notation-explained and /blog/sorting-algorithms-overview, which both use logarithmic structures.

Wrap up

Segment trees give O(log n) range queries and updates on any associative aggregate. The iterative version is short and fast, the recursive version is easier to extend with lazy propagation, and the data structure is the workhorse of competitive programming. Master it once, reuse it forever.