Understanding Segment Trees: A Competitive Programmer's Deep Dive

Segment trees are one of the most powerful data structures in competitive programming. Once you internalize them, a whole class of range-query problems becomes trivial.

What Problem Does It Solve?

Given an array of $n$ elements, you want to:

1. Query an aggregate (sum, min, max, GCD…) over a range $[l, r]$ in $O(\log n)$.
2. Update a single element — or an entire range — also in $O(\log n)$.

A naive prefix sum handles static range-sum queries in $O(1)$, but breaks the moment you update. A segment tree handles both operations efficiently.

Structure

A segment tree is a complete binary tree where:

• Leaf nodes represent individual array elements.
• Internal nodes store the aggregate of their children’s ranges.

For an array of size $n$, the tree has at most $4n$ nodes — so we typically allocate int tree[4 * MAXN].

const int MAXN = 1e5 + 5;
int tree[4 * MAXN];
int arr[MAXN];

Build

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

Build runs in $O(n)$ — each of the $n$ leaves is visited once, and internal nodes are simply sums of their children.

Point Query / Range Sum

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;           // out of range
    if (l <= start && end <= r) return tree[node]; // fully inside
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r)
         + query(2 * node + 1, mid + 1, end, l, r);
}

Lazy Propagation

When you need range updates (e.g., add $v$ to every element in $[l, r]$), re-computing each leaf is $O(n)$. Lazy propagation defers updates: we mark a node as “pending” and push the update down only when we need to visit its children.

int lazy[4 * MAXN];

void pushDown(int node, int start, int end) {
    if (lazy[node] != 0) {
        int mid = (start + end) / 2;
        int leftLen  = mid - start + 1;
        int rightLen = end - mid;

        tree[2 * node]     += lazy[node] * leftLen;
        tree[2 * node + 1] += lazy[node] * rightLen;
        lazy[2 * node]     += lazy[node];
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
}

void updateRange(int node, int start, int end, int l, int r, int val) {
    if (r < start || end < l) return;
    if (l <= start && end <= r) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    pushDown(node, start, end);
    int mid = (start + end) / 2;
    updateRange(2 * node, start, mid, l, r, val);
    updateRange(2 * node + 1, mid + 1, end, l, r, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Real Contest Application

Problem: You’re given an array. Handle $Q$ queries of two types:

• 1 l r v — add $v$ to all elements in $[l, r]$
• 2 l r — output the sum of elements in $[l, r]$

This is the canonical lazy segment tree problem. With the implementation above it runs in $O(Q \log n)$ — fast enough for $n, Q \leq 10^5$ with room to spare.

Key Takeaways

• Always think about what your merge function is. For min/max/GCD, swap out the + in the build and query steps.
• Lazy propagation only makes sense when range updates are needed. Point updates don’t require it.
• Practice on Codeforces 339D for a non-trivial lazy application.

Segment trees become second nature after 20–30 problems. Start with pure range sums, then move to min/max variants, then tackle merge-sort trees and persistent variants.