templates · Bits, range queries & string matching

Segment tree

  • Many range queries (sum, min, max) mixed with updates
  • The query is not a plain sum, so a Fenwick tree does not fit (range min or max)
  • n and the number of queries are both up to about 10⁵

Segment tree

the one rule

The invariant

Every node holds combine of exactly its range [lo..hi], and its children split that range at mid.

write it from memory

The template

javajava.util.*
/** Range query + point update. Change `combine` and `IDENTITY` to switch between sum, min and max. */class SegTree {    private static final long IDENTITY = 0;              // sum: 0, min: Long.MAX_VALUE, max: Long.MIN_VALUE    private final long[] tree;                           // tree[node] = combine of its whole range    private final int n;     SegTree(int[] values) {        n = values.length;        tree = new long[4 * Math.max(1, n)];             // 4n is always enough        if (n > 0) build(1, 0, n - 1, values);    }     private static long combine(long a, long b) {        return a + b;                                    // the ONE line to change: Math.min / Math.max    }     private void build(int node, int lo, int hi, int[] values) {        if (lo == hi) {            tree[node] = values[lo];                     // leaf            return;        }        int mid = (lo + hi) / 2;        build(2 * node, lo, mid, values);        build(2 * node + 1, mid + 1, hi, values);        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);    }     /** values[index] = value */    void set(int index, long value) {        set(1, 0, n - 1, index, value);    }     private void set(int node, int lo, int hi, int index, long value) {        if (lo == hi) {            tree[node] = value;                          // assign (or += for "add to")            return;        }        int mid = (lo + hi) / 2;        if (index <= mid) set(2 * node, lo, mid, index, value);        else set(2 * node + 1, mid + 1, hi, index, value);        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);    }     /** combine of values[left..right], both inclusive */    long query(int left, int right) {        return query(1, 0, n - 1, left, right);    }     private long query(int node, int lo, int hi, int left, int right) {        if (right < lo || hi < left) return IDENTITY;    // no overlap        if (left <= lo && hi <= right) return tree[node]; // fully inside        int mid = (lo + hi) / 2;                         // partial: ask both children        return combine(query(2 * node, lo, mid, left, right), query(2 * node + 1, mid + 1, hi, left, right));    }}

Node 1 is the root; the children of node are 2 * node and 2 * node + 1, the same layout as a heap.

fill in the blanks — only these lines change per problem

  1. line 14The operation: a + b, Math.min(a, b), Math.max(a, b), or a gcd.
  2. line 3The value that changes nothing: 0 for sum, Long.MAX_VALUE for min, Long.MIN_VALUE for max.
  3. line 35Assign the new value, or += if the problem says "add to".
  4. line 50No overlap returns the identity, so it never changes the result.

complexity

What it costs

time O(n) build, O(log n) per update or query
Build visits each of about 2n nodes once. The tree is log₂ n levels deep, and a query touches at most 4 nodes per level.
space O(n)
An array of 4n nodes is always enough for a tree over n leaves.

watch out

Common bugs

  • Sizing the array 2n. For n that is not a power of two the recursive layout needs up to 4n.
  • Returning 0 for "no overlap" in a min query. Use the identity of your operation.
  • Forgetting to recombine the parent after updating a child.

use it

Practise it on

learn it properly