Understanding Segment Trees from Scratch

What is a segment tree?

A segment tree stores information about array ranges in a binary tree. After an O(n) build, point updates and range queries each take O(log n) time.

Building the tree

int tree[4 * MAXN];

void build(int node, int start, int end, int arr[]) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }

    int mid = (start + end) / 2;
    build(node * 2, start, mid, arr);
    build(node * 2 + 1, mid + 1, end, arr);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

Range-sum query

int query(int node, int start, int end, int left, int right) {
    if (right < start || end < left) return 0;
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;
    return query(node * 2, start, mid, left, right)
         + query(node * 2 + 1, mid + 1, end, left, right);
}

The same structure can support minimums, maximums, greatest common divisors, and more complex range data by changing the merge operation.