Segment tree

Answer range questions like "sum of a[l..r]" while the array keeps changing. Both updates and queries take O(log n).

what

A binary tree over the array where every node stores the answer (here, the sum) for one range. A query combines O(log n) nodes; an update fixes one root-to-leaf path.

use when

Range sum, min, max or gcd queries mixed with changes to single elements, too many of each to recompute from scratch.

time

O(log n) per update and query, O(n) to build

space

O(n): a 4n array

You’ll recognise it when

You need the sum, minimum or maximum of a range a[l..r], many times.
The array changes between questions: single elements get set or increased.
Both kinds of operation come in large numbers, say 10⁵ each, so O(n) per operation is too slow.
The combining operation is associative (sum, min, max, gcd, xor), even if it can’t be undone.

If the array never changes, a prefix-sum array answers range sums in O(1) and is far simpler. For sums with point updates, a Fenwick tree is shorter to write; the segment tree is the one that also handles min, max and range updates.

The idea

Think of a company’s sales report. Each shop knows its own total, each region adds up its shops, each country adds up its regions. To answer “total for shops 3 to 12”, you don’t add ten shops: you take a couple of whole regions that lie inside the range, plus a shop or two at the edges. When one shop’s number changes, only its region and country totals need fixing.

A segment tree is that report for an array. The root covers the whole array, each node’s two children split its range in half, and the leaves are single elements. Every node stores the sum of its range. Any range [l, r] can be glued together from a handful of nodes, and one element sits under only one node per level.

How it works

Nodes are numbered like a heap: node 1 is the root, and the children of node k are 2k and 2k + 1. Each call knows the range [lo, hi] that its node covers. Scroll through the steps and the graphic follows along; the array is the bottom row and every box above shows its range and its sum.

Build, leaves: a node whose range is a single index [i, i] stores a[i].
Build, the rest: every other node stores its left child’s sum plus its right child’s sum, filled in from the bottom up.
query(l, r) starts at the root and compares the node’s range [lo, hi] with the query range [l, r]. There are only three cases.
Partial overlap: some of the node is inside the query and some isn’t, so its sum is useless as it is. Split at mid and ask both children.
Outside: the node’s range misses [l, r] completely. Return 0 and don’t look below it.
Fully inside: every index under the node is wanted. Return its stored sum and don’t look below it either.
The recursion adds the children’s answers on the way back up, so the root returns total, the sum of the green nodes.
update(i, value) walks from the root towards index i: left if i ≤ mid, right otherwise.
At the leaf [i, i], overwrite the old value. Every node above it now holds a stale sum.
On the way back up, each node on the path adds its two children again. No node off the path covers i, so nothing else changes.

loading segment-tree…

Why is the answer right? The green nodes cover [l, r] exactly: every index in the range lies under exactly one fully inside node, because a node is only split when it’s partial, and a split’s two children don’t overlap. Adding their sums adds each wanted element once.

class SegmentTree:
    """Range sums with point updates. Node 1 covers the whole array, and
    node k's children are 2k (left half) and 2k + 1 (right half)."""

    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (4 * self.n)
        if self.n:
            self._build(a, 1, 0, self.n - 1)

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

    def update(self, i, value):
        """Set a[i] = value."""
        self._update(1, 0, self.n - 1, i, value)

    def _update(self, node, lo, hi, i, value):
        if lo == hi:
            self.t[node] = value
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._update(2 * node, lo, mid, i, value)
        else:
            self._update(2 * node + 1, mid + 1, hi, i, value)
        self.t[node] = self.t[2 * node] + self.t[2 * node + 1]

    def query(self, l, r):
        """Sum of a[l..r], both ends included."""
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, lo, hi, l, r):
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.t[node]
        mid = (lo + hi) // 2
        total = self._query(2 * node, lo, mid, l, r)
        total += self._query(2 * node + 1, mid + 1, hi, l, r)
        return total

#include <vector>
using namespace std;

// Range sums with point updates. Node 1 covers the whole array, and
// node k's children are 2k (left half) and 2k + 1 (right half).
struct SegmentTree {
    int n;
    vector<long long> t;

    SegmentTree(const vector<long long>& a) : n(a.size()), t(4 * a.size()) {
        if (n) build(a, 1, 0, n - 1);
    }

    void build(const vector<long long>& a, int node, int lo, int hi) {
        if (lo == hi) {
            t[node] = a[lo];
            return;
        }
        int mid = (lo + hi) / 2;
        build(a, 2 * node, lo, mid);
        build(a, 2 * node + 1, mid + 1, hi);
        t[node] = t[2 * node] + t[2 * node + 1];
    }

    // Set a[i] = value.
    void update(int i, long long value) {
        update(1, 0, n - 1, i, value);
    }

    void update(int node, int lo, int hi, int i, long long value) {
        if (lo == hi) {
            t[node] = value;
            return;
        }
        int mid = (lo + hi) / 2;
        if (i <= mid) {
            update(2 * node, lo, mid, i, value);
        } else {
            update(2 * node + 1, mid + 1, hi, i, value);
        }
        t[node] = t[2 * node] + t[2 * node + 1];
    }

    // Sum of a[l..r], both ends included.
    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) {
            return 0;
        }
        if (l <= lo && hi <= r) {
            return t[node];
        }
        int mid = (lo + hi) / 2;
        long long total = query(2 * node, lo, mid, l, r);
        total += query(2 * node + 1, mid + 1, hi, l, r);
        return total;
    }
};

// Range sums with point updates. Node 1 covers the whole array, and
// node k's children are 2k (left half) and 2k + 1 (right half).
class SegmentTree {
    private final int n;
    private final long[] t;

    SegmentTree(long[] a) {
        n = a.length;
        t = new long[4 * Math.max(n, 1)];
        if (n > 0) build(a, 1, 0, n - 1);
    }

    private void build(long[] a, int node, int lo, int hi) {
        if (lo == hi) {
            t[node] = a[lo];
            return;
        }
        int mid = (lo + hi) / 2;
        build(a, 2 * node, lo, mid);
        build(a, 2 * node + 1, mid + 1, hi);
        t[node] = t[2 * node] + t[2 * node + 1];
    }

    /** Set a[i] = value. */
    void update(int i, long value) {
        update(1, 0, n - 1, i, value);
    }

    private void update(int node, int lo, int hi, int i, long value) {
        if (lo == hi) {
            t[node] = value;
            return;
        }
        int mid = (lo + hi) / 2;
        if (i <= mid) {
            update(2 * node, lo, mid, i, value);
        } else {
            update(2 * node + 1, mid + 1, hi, i, value);
        }
        t[node] = t[2 * node] + t[2 * node + 1];
    }

    /** Sum of a[l..r], both ends included. */
    long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    private long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) {
            return 0;
        }
        if (l <= lo && hi <= r) {
            return t[node];
        }
        int mid = (lo + hi) / 2;
        long total = query(2 * node, lo, mid, l, r);
        total += query(2 * node + 1, mid + 1, hi, l, r);
        return total;
    }
}

The recursion is only about log₂ n deep (17 levels for 10⁵ elements), so recursion is safe even in Python. The sums use 64-bit integers: 10⁵ values of 10⁹ add up to 10¹⁴, far past a 32-bit int.

Why it’s O(log n)

An update visits one node per level, and a tree over n elements has about log₂ n + 1 levels.

A query can’t touch many nodes per level either. A partial node must contain one of the query’s two ends, l or r, and on any level only two nodes do. So at most 2 nodes per level are partial, and only partial nodes have their children visited: at most 4 visited nodes per level, about 4 log₂ n in total. For 10⁶ elements that’s about 80 nodes at most, instead of up to a million cells.

Build fills each node once from its two children, and there are fewer than 2n nodes: O(n).

Operation	Time
build	O(n)
`update(i, value)`	O(log n)
`query(l, r)`	O(log n)
memory	4n slots

Why 4n slots? With heap numbering, the deepest level is the first power of two ≥ n, and indexes run up to about twice that. When n is just over a power of two, that’s close to 4n, so 4 * n is always enough. The tree itself has only 2n − 1 nodes; the rest are unused gaps.

Common mistakes

Allocating 2n slots for the recursive tree

The tree has 2n − 1 nodes, but heap numbering leaves gaps when n isn’t a power of two, so indexes go past 2n. It works for n = 8 and crashes (or silently corrupts memory in C++) for n = 6, whose last leaf is node 13.

t = [0] * (2 * n)    # ✗ node 2k + 1 can be past the end
t = [0] * (4 * n)    # ✓ always enough for this numbering

Returning 0 for “outside” in a min tree

The outside case must return a value that can’t change the answer: 0 for sums, but +∞ for min and −∞ for max. In a min tree over positive numbers, a 0 from any skipped node becomes the answer.

if r < lo or hi < l: return 0              # ✗ in a min tree
if r < lo or hi < l: return float("inf")   # ✓ the identity for min

Mixing inclusive and half-open ranges

This code treats query(l, r) as inclusive at both ends. Calling it with a half-open range like query(l, r + 1), or the other way round, silently includes or drops one element and never crashes. Pick one convention, write it in a comment, and convert at the call site.

32-bit sums

Each value fits in an int, but the root holds the sum of all of them. In C++ and Java, store the tree as long long / long, or large tests overflow without warning.

vector<int> t;          // ✗ 10⁵ × 10⁹ overflows
vector<long long> t;    // ✓

Variations

Range min or max. Swap + for min or max and return the matching identity (+∞ or −∞) from the outside case. Anything associative works the same way: gcd, xor, or a small struct such as “max subarray sum in this range”.
Lazy propagation for range updates. To add x to a whole range, don’t touch every leaf: stop at fully inside nodes, update their sums, and leave a pending “add x” note on them. Push that note down to the children the next time any operation needs to go below. Range updates and queries both stay O(log n).
Iterative bottom-up tree. Store the leaves at t[n..2n) and parent k at t[k] = t[2k] + t[2k+1]. A query climbs from both ends of the range towards the root. It needs only 2n slots, has no recursion and runs faster, but is harder to extend with lazy updates.
Compared with a Fenwick tree. A Fenwick tree does point update and prefix sum in about ten lines and n + 1 slots, but a range answer comes from prefix(r) − prefix(l − 1), which needs subtraction. So it can’t do range min or max; a segment tree can.
Walking the tree. “First index where the prefix sum reaches k” or “first element ≥ x in a range” can be answered in one O(log n) descent, by choosing the left or right child from the stored values.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
An array of 10⁵ numbers gets 10⁵ operations, each either “set a[i] = x” or “what is the minimum of a[l..r]?”. Which structure fits?
A segment tree works for any associative operation, including min, and handles both operations in O(log n). The Fenwick subtraction trick only works for sums (min can’t be “subtracted”), rebuilding a prefix array costs O(n) per change, and a heap only knows the global minimum, not the minimum of a range.

This sum tree counts how many nodes a query visits. What does it print?

a = [2, 1, 5, 3, 4, 6]
n = len(a)
t = [0] * (4 * n)
def build(node, lo, hi):
    if lo == hi:
        t[node] = a[lo]; return
    mid = (lo + hi) // 2
    build(2 * node, lo, mid); build(2 * node + 1, mid + 1, hi)
    t[node] = t[2 * node] + t[2 * node + 1]
visits = 0
def query(node, lo, hi, l, r):
    global visits
    visits += 1
    if r < lo or hi < l: return 0
    if l <= lo and hi <= r: return t[node]
    mid = (lo + hi) // 2
    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r)
build(1, 0, n - 1)
print(query(1, 0, n - 1, 1, 4), visits)

A min tree copied from a sum tree kept return 0 for the outside case. What does it print?

a = [4, 7, 2, 9, 5]
n = len(a)
t = [0] * (4 * n)
def build(node, lo, hi):
    if lo == hi:
        t[node] = a[lo]; return
    mid = (lo + hi) // 2
    build(2 * node, lo, mid); build(2 * node + 1, mid + 1, hi)
    t[node] = min(t[2 * node], t[2 * node + 1])
def query(node, lo, hi, l, r):     # min of a[l..r]
    if r < lo or hi < l: return 0
    if l <= lo and hi <= r: return t[node]
    mid = (lo + hi) // 2
    return min(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r))
build(1, 0, n - 1)
print(query(1, 0, n - 1, 0, 4), query(1, 0, n - 1, 1, 3))

4
For a segment tree over n elements, what do build, point update and range query cost?
Build computes each of the fewer than 2n nodes once from its two children, so it’s O(n), not O(n log n). An update fixes one root-to-leaf path, and a query has at most 2 partial nodes per level, so both are O(log n). O(1) range queries belong to a sparse table, which can’t be updated cheaply.
5
A recursive segment tree numbers nodes like a heap (root 1, children 2k and 2k + 1). Why is its array usually sized 4 * n?
The tree has only 2n − 1 nodes, but heap numbering reserves slots as if the bottom level were full, so for n = 6 the last leaf is node 13, past 2n = 12. The largest index stays below 4n. Each element is stored in about log₂ n nodes (one per level), not 4.