Segment Trees: Fast Range Queries & Updates

A Segment Tree is a binary tree built over an array that lets you answer range queries (sum, min, max, gcd…) and apply updates in O(log n) each, even as the underlying values keep changing. A plain array gives O(1) updates but O(n) range sums; a prefix-sum array gives O(1) range sums but O(n) updates. The segment tree balances both at O(log n), which is why it’s the standard answer to “range sum query — mutable”.

The idea

Each node stores the aggregate (here, the sum) of a contiguous segment of the array. The root covers the whole array [0, n); each node splits its range in half between two children, down to leaves that cover a single element. Any query range can be assembled from O(log n) of these precomputed segments.

We store the tree in a flat array tree of size 2n using the simple convention: leaf i sits at tree[n + i], and the parent of node k is tree[k >> 1]. This iterative layout is compact and fast.

Building the tree

Copy the input into the leaves, then fill internal nodes bottom-up: each parent is the sum of its two children.

struct SegTree {
    int n;
    std::vector<long long> tree;
    SegTree(const std::vector<int>& a) : n(a.size()), tree(2 * a.size()) {
        for (int i = 0; i < n; i++) tree[n + i] = a[i];      // leaves
        for (int i = n - 1; i > 0; i--)                       // internal nodes
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
};

class SegTree {
    int n;
    long[] tree;
    SegTree(int[] a) {
        n = a.length;
        tree = new long[2 * n];
        for (int i = 0; i < n; i++) tree[n + i] = a[i];      // leaves
        for (int i = n - 1; i > 0; i--)                       // internal nodes
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
}

class SegTree {
  constructor(a) {
    this.n = a.length;
    this.tree = new Array(2 * this.n).fill(0);
    for (let i = 0; i < this.n; i++) this.tree[this.n + i] = a[i];   // leaves
    for (let i = this.n - 1; i > 0; i--)                              // internal nodes
      this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
  }
}

class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):                  # leaves
            self.tree[self.n + i] = a[i]
        for i in range(self.n - 1, 0, -1):       # internal nodes
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

Point update

To set a[i] = value, write the leaf, then walk up to the root recomputing each parent from its two children.

void update(int i, long long value) {
    i += n;
    tree[i] = value;
    for (i >>= 1; i >= 1; i >>= 1)
        tree[i] = tree[2 * i] + tree[2 * i + 1];
}

void update(int i, long value) {
    i += n;
    tree[i] = value;
    for (i >>= 1; i >= 1; i >>= 1)
        tree[i] = tree[2 * i] + tree[2 * i + 1];
}

update(i, value) {
  i += this.n;
  this.tree[i] = value;
  for (i >>= 1; i >= 1; i >>= 1)
    this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
}

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

Range query

To sum [l, r) (left inclusive, right exclusive), start at the leaves and move up. Whenever a boundary is a right child, it lies fully inside the range — add it and step inward; same on the right end. This sweeps O(log n) segments.

long long query(int l, int r) {   // sum of [l, r)
    long long res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res += tree[l++];
        if (r & 1) res += tree[--r];
    }
    return res;
}

long query(int l, int r) {        // sum of [l, r)
    long res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if ((l & 1) == 1) res += tree[l++];
        if ((r & 1) == 1) res += tree[--r];
    }
    return res;
}

query(l, r) {                     // sum of [l, r)
  let res = 0;
  for (l += this.n, r += this.n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res += this.tree[l++];
    if (r & 1) res += this.tree[--r];
  }
  return res;
}

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

Going deeper: Swap + for min/max/gcd (and the identity element from 0 to +∞/-∞/0) and the same structure answers range-minimum, range-maximum, or range-gcd queries. For range updates (add a value to a whole range) you add lazy propagation on top.

Complexity

Operation	Time	Space
Build	O(n)	O(n)
Point update	O(log n)	—
Range query	O(log n)	—

Common pitfalls

Half-open vs closed ranges. This implementation uses [l, r). To query the closed range [l, r], call query(l, r + 1). Pick one convention and stay consistent.
Overflow. Sums of many large ints overflow 32-bit types — use 64-bit accumulators (long long / long).
Forgetting to update ancestors. After writing a leaf you must recompute every ancestor, not just the immediate parent.

When to use it

Use a segment tree when values change and you need range aggregates: mutable range-sum/min/max queries, and as a building block for harder problems. If values never change, a prefix-sum array is simpler. If you only need prefix sums with point updates, a Fenwick tree is lighter and faster to code.

Practice on the advanced exercises.