Chapter 98

Home

Segment Trees: Range Queries

A segment tree is a binary tree storing aggregate data (sum, min, max) over intervals. Point updates and range queries in O(log N). More flexible than Fenwick tree — handles any associative operation.

Segment Tree for Range Sum

C++ — recursive segment tree

struct SegTree {
    vector tree;
    int n;

    SegTree(vector& arr) {
        n = arr.size();
        tree.assign(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    void build(vector& arr, int node, int l, int r) {
        if (l == r) { tree[node] = arr[l]; return; }
        int mid = (l + r) / 2;
        build(arr, node * 2, l, mid);
        build(arr, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    void update(int pos, long long val, int node, int l, int r) {
        if (l == r) { tree[node] = val; return; }
        int mid = (l + r) / 2;
        if (pos <= mid) update(pos, val, node * 2, l, mid);
        else update(pos, val, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

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

// O(log N) per query/update. Memory: O(4N).

Key Takeaways