Segment Tree

The problem

You have an array of numbers and two kinds of requests arriving thousands of times:

1. Query: what is the sum (or min, or max) of a[l..r]?
2. Update: change a[i] to a new value.

When both operations are frequent, the segment tree wins.

The structure

A segment tree is a binary tree where:

• each leaf holds one array element,
• each internal node covers a segment [l..r] and stores the sum of that segment,
• a node covering [l..r] has children covering [l..mid] and [mid+1..r].

The root covers the whole array. In the model, each node shows its sum, and the tag below it shows its range.

It’s stored in an array of size about 2n (or 4n for safety): node k has children 2k and 2k + 1 — the same trick as a binary heap.

Range query: three cases

Starting at the root, for each node compare its range [l..r] with the query [ql..qr]:

1. No overlap (completely outside) → return 0 (grey).
2. Total overlap (completely inside) → return the stored sum, don’t go deeper (green).
3. Partial overlap → ask both children and add the answers (yellow).

Because only O(1) nodes per level are partially overlapping, a query visits O(log n) nodes.

Point update

Change the leaf, then walk up to the root recomputing node = left + right. That’s one node per level: O(log n).

Code

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

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

    def query(self, ql, qr, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if qr < l or r < ql:            # no overlap
            return 0
        if ql <= l and r <= qr:          # total overlap
            return self.t[node]
        mid = (l + r) // 2               # partial overlap
        return (self.query(ql, qr, 2 * node, l, mid) +
                self.query(ql, qr, 2 * node + 1, mid + 1, r))

    def update(self, i, value, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        if l == r:
            self.t[node] = value
            return
        mid = (l + r) // 2
        if i <= mid:
            self.update(i, value, 2 * node, l, mid)
        else:
            self.update(i, value, 2 * node + 1, mid + 1, r)
        self.t[node] = self.t[2 * node] + self.t[2 * node + 1]

st = SegmentTree([5, 3, 8, 6, 1, 4, 7, 2])
print(st.query(2, 6))   # 8+6+1+4+7 = 26
st.update(3, 10)
print(st.query(2, 6))   # 30

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<long long> t;

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

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

void update(int node, int l, int r, int i, int v) {
    if (l == r) { t[node] = v; return; }
    int mid = (l + r) / 2;
    if (i <= mid) update(2 * node, l, mid, i, v);
    else update(2 * node + 1, mid + 1, r, i, v);
    t[node] = t[2 * node] + t[2 * node + 1];
}

int main() {
    vector<int> a = {5, 3, 8, 6, 1, 4, 7, 2};
    n = a.size();
    t.assign(4 * n, 0);
    build(a, 1, 0, n - 1);
    cout << query(1, 0, n - 1, 2, 6) << "\n";   // 26
}

Variations

• Min / max / GCD segment trees: replace + with min, max or gcd.
• Lazy propagation: update a whole range [l..r] in O(log n) by postponing work.
• Fenwick tree (Binary Indexed Tree): a simpler, smaller structure for prefix sums with updates.

Where is it used?

Competitive programming, stock-price analytics (max over a time window), computational geometry, and games that need fast range statistics on changing data.

Common mistakes

• Allocating only 2n slots with recursive 1-based indexing — use 4n to be safe.
• Mixing up inclusive and exclusive range ends.
• Forgetting to recompute the parent after updating a child.