Segment Tree

The Problem

Given an array of n elements, we need to efficiently support two kinds of operations:

Query: Compute an aggregate (sum, min, max, GCD, ...) over any subarray [l, r]
Update: Modify one element (point update) or a range of elements (range update)

Why not simpler approaches?

The segment tree is the Swiss Army knife of range query data structures. It handles any associative operation -- sum, min, max, GCD, bitwise OR/AND, matrix multiplication -- with both point and range updates.

Structure -- A Binary Tree Over an Array

A segment tree is a full binary tree where:

Each leaf corresponds to one array element.
Each internal node stores the aggregate of its two children.
The root stores the aggregate of the entire array.

Array: a = [2, 1, 5, 3, 4, 2] (0-indexed, n=6)

Segment tree (sum):

Indexing Convention

We use 1-based indexing for the tree array:

Root is at index 1
Node i's left child: 2*i
Node i's right child: 2*i + 1
Node i's parent: i / 2

Size of the array: We allocate 4*n to be safe. (The exact size needed is 2 * next_power_of_2(n), but 4*n always works and is simpler.)

Why 4*n?
  - A full binary tree with n leaves has 2n - 1 nodes.
  - But we use 1-based indexing, so we need indices up to about 2n.
  - When n is not a power of 2, the tree is not perfectly full,
    and some indices can go up to 4*n - 5.
  - 4*n is a safe upper bound.

Build -- O(n)

Build the tree bottom-up recursively. Each leaf gets an array element. Each internal node is the merge of its children.

CPP

const int MAXN = 200005;
int tree[4 * MAXN];
int arr[MAXN];
int n;

void build(int node, int start, int end) {
    if (start == end) {
        // Leaf: store the array element
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid);       // build left child
    build(2 * node + 1, mid + 1, end); // build right child
    tree[node] = tree[2 * node] + tree[2 * node + 1]; // merge
}

// Usage: build(1, 0, n-1);

Visual walkthrough of build for [2, 1, 5, 3, 4, 2]:

build(1, 0, 5)
  build(2, 0, 2)
    build(4, 0, 1)
      build(8, 0, 0) -> tree[8] = arr[0] = 2
      build(9, 1, 1) -> tree[9] = arr[1] = 1
      tree[4] = 2 + 1 = 3
    build(5, 2, 2) -> tree[5] = arr[2] = 5
    tree[2] = 3 + 5 = 8
  build(3, 3, 5)
    build(6, 3, 4)
      build(12, 3, 3) -> tree[12] = arr[3] = 3
      build(13, 4, 4) -> tree[13] = arr[4] = 4
      tree[6] = 3 + 4 = 7
    build(7, 5, 5) -> tree[7] = arr[5] = 2
    tree[3] = 7 + 2 = 9
  tree[1] = 8 + 9 = 17

Time: O(n). Each of the ~2n nodes is visited exactly once.

Point Update -- O(log n)

To update arr[idx] = val, walk from root to the leaf at idx, update the leaf, then recalculate all ancestors on the way back up.

CPP

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // Reached the leaf
        arr[idx] = val;
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid)
        update(2 * node, start, mid, idx, val);
    else
        update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1]; // re-merge
}

// Usage: update(1, 0, n-1, idx, val);

Visual walkthrough: update arr[2] from 5 to 7

Before:

update(1, 0, 5, 2, 7):
  mid = 2, idx=2 <= 2 -> go left
  update(2, 0, 2, 2, 7):
    mid = 1, idx=2 > 1 -> go right
    update(5, 2, 2, 2, 7):
      start == end -> tree[5] = 7  (was 5)
    tree[2] = tree[4] + tree[5] = 3 + 7 = 10  (was 8)
  tree[1] = tree[2] + tree[3] = 10 + 9 = 19  (was 17)

After: (only 3 nodes changed along the root-to-leaf path -- O(log n))

Range Query -- O(log n)

To compute the aggregate over [l, r], we recursively check each node:

Three cases at node covering [start, end]:

Case 1: [start, end] is completely INSIDE [l, r]
  -> Return tree[node] immediately (no need to recurse deeper)

Case 2: [start, end] is completely OUTSIDE [l, r]
  -> Return identity element (0 for sum, INT_MAX for min, etc.)

Case 3: [start, end] PARTIALLY overlaps [l, r]
  -> Recurse into both children and merge results

CPP

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l)          // Case 2: no overlap
        return 0;                       // identity for sum
    if (l <= start && end <= r)         // Case 1: total overlap
        return tree[node];
    // Case 3: partial overlap
    int mid = (start + end) / 2;
    int leftResult = query(2 * node, start, mid, l, r);
    int rightResult = query(2 * node + 1, mid + 1, end, l, r);
    return leftResult + rightResult;
}

// Usage: query(1, 0, n-1, l, r);

Visual walkthrough: query(1, 4) on array [2, 1, 5, 3, 4, 2]

We want sum of a[1] + a[2] + a[3] + a[4] = 1 + 5 + 3 + 4 = 13.

query(1, 0, 5, 1, 4):
  Partial overlap [0,5] vs [1,4]
  |
  +-- query(2, 0, 2, 1, 4):
  |     Partial overlap [0,2] vs [1,4]
  |     |
  |     +-- query(4, 0, 1, 1, 4):
  |     |     Partial overlap [0,1] vs [1,4]
  |     |     |
  |     |     +-- query(8, 0, 0, 1, 4):
  |     |     |     [0,0] vs [1,4]: NO overlap -> return 0
  |     |     |
  |     |     +-- query(9, 1, 1, 1, 4):
  |     |           [1,1] inside [1,4]: TOTAL overlap -> return 1
  |     |
  |     |     return 0 + 1 = 1
  |     |
  |     +-- query(5, 2, 2, 1, 4):
  |           [2,2] inside [1,4]: TOTAL overlap -> return 5
  |
  |     return 1 + 5 = 6
  |
  +-- query(3, 3, 5, 1, 4):
        Partial overlap [3,5] vs [1,4]
        |
        +-- query(6, 3, 4, 1, 4):
        |     [3,4] inside [1,4]: TOTAL overlap -> return 7
        |
        +-- query(7, 5, 5, 1, 4):
              [5,5] vs [1,4]: NO overlap -> return 0

        return 7 + 0 = 7

  return 6 + 7 = 13  CORRECT!

Nodes visited: 1, 2, 3, 4, 5, 6, 7, 8, 9 = 9 nodes
But at most O(4 * log n) nodes are visited (provably).

Why O(log n)? At each level of the tree, at most 4 nodes are visited (at most 2 partial overlaps per side). Since the tree has O(log n) levels, total work is O(log n).

More precisely: at each level, at most 2 nodes split into children (partial overlap). All other nodes either return immediately (total overlap or no overlap). So at most 2 * log(n) + 2 nodes are visited.

Lazy Propagation -- Range Updates in O(log n)

The Problem with Naive Range Updates

To add delta to all elements in [l, r] without lazy propagation, we'd call point update for each index: O((r - l + 1) * log n) = O(n log n) in the worst case. Terrible!

The Lazy Idea

Instead of immediately updating all affected leaves, we store a pending operation (called "lazy" value) at internal nodes and push it down only when needed.

Principle: When a range update completely covers a node's range, update the node's aggregate value and store the lazy value -- don't recurse into children. When a later query or update needs to access the children, push the lazy value down first.

Visual Walkthrough: Range Add +3 to [1, 4]

Array: a = [2, 1, 5, 3, 4, 2]

Before:

Range update: add 3 to [1, 4]

Step 1: query node 1 [0,5] -- partial overlap with [1,4]
  Recurse into children.

Step 2: node 2 [0,2] -- partial overlap with [1,4]
  Recurse into children.

Step 3: node 4 [0,1] -- partial overlap with [1,4]
  Recurse into children.

Step 4: node 8 [0,0] -- NO overlap with [1,4]
  Return without change.

Step 5: node 9 [1,1] -- TOTAL overlap with [1,4]
  tree[9] += 3*1 = 3  -->  tree[9] = 1 + 3 = 4
  lazy[9] += 3  (but it's a leaf, so lazy is irrelevant)

Step 6: Back at node 4, merge: tree[4] = tree[8] + tree[9] = 2 + 4 = 6

Step 7: node 5 [2,2] -- TOTAL overlap with [1,4]
  tree[5] += 3*1 = 3  -->  tree[5] = 5 + 3 = 8
  lazy[5] += 3

Step 8: Back at node 2, merge: tree[2] = tree[4] + tree[5] = 6 + 8 = 14

Step 9: node 3 [3,5] -- partial overlap with [1,4]
  Recurse into children.

Step 10: node 6 [3,4] -- TOTAL overlap with [1,4]!
  tree[6] += 3*2 = 6  -->  tree[6] = 7 + 6 = 13
  lazy[6] += 3
  DO NOT recurse further!  This is the power of lazy propagation.

Step 11: node 7 [5,5] -- NO overlap with [1,4]
  Return without change.

Step 12: Back at node 3, merge: tree[3] = tree[6] + tree[7] = 13 + 2 = 15

Step 13: Back at node 1, merge: tree[1] = tree[2] + tree[3] = 14 + 15 = 29

After:

What happens when we later query [3, 3]?

query(1, 0, 5, 3, 3):
  -> query(3, 3, 5, 3, 3):
    -> query(6, 3, 4, 3, 3):
       Partial overlap! Before recursing, PUSH DOWN lazy[6]=3:
         tree[12] += 3*1 = 6  (was 3)
         tree[13] += 3*1 = 7  (was 4)
         lazy[12] += 3
         lazy[13] += 3
         lazy[6] = 0
       Now recurse:
       -> query(12, 3, 3, 3, 3): total overlap -> return 6
       -> query(13, 4, 4, 3, 3): no overlap -> return 0
       return 6

Answer: 6 = original a[3] + 3 = 3 + 3 = 6.  Correct!

Complete Implementation with Lazy Propagation

CPP

#include <bits/stdc++.h>
using namespace std;

class SegTree {
    int n;
    vector<long long> tree, lazy;

    // Push pending lazy updates to children
    void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            // Apply lazy value to current node
            tree[node] += lazy[node] * (end - start + 1);

            if (start != end) {
                // Propagate to children (don't apply yet, just accumulate)
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0; // clear lazy for this node
        }
    }

    void build(vector<int>& arr, int node, int start, int end) {
        lazy[node] = 0;
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void updateRange(int node, int start, int end, int l, int r, long long val) {
        pushDown(node, start, end); // always push down first

        if (r < start || end < l) return;          // no overlap

        if (l <= start && end <= r) {               // total overlap
            lazy[node] += val;
            pushDown(node, start, end);             // apply immediately
            return;
        }

        // partial overlap
        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];
    }

    long long queryRange(int node, int start, int end, int l, int r) {
        pushDown(node, start, end); // always push down first

        if (r < start || end < l) return 0;         // no overlap

        if (l <= start && end <= r) return tree[node]; // total overlap

        // partial overlap
        int mid = (start + end) / 2;
        return queryRange(2 * node, start, mid, l, r) +
               queryRange(2 * node + 1, mid + 1, end, l, r);
    }

public:
    SegTree() : n(0) {}

    SegTree(vector<int>& arr) : n(arr.size()), tree(4 * n, 0), lazy(4 * n, 0) {
        if (n > 0) build(arr, 1, 0, n - 1);
    }

    SegTree(int n, int initVal = 0) : n(n), tree(4 * n, 0), lazy(4 * n, 0) {
        vector<int> arr(n, initVal);
        if (n > 0) build(arr, 1, 0, n - 1);
    }

    // Range update: add val to all elements in [l, r] (0-indexed)
    void update(int l, int r, long long val) {
        updateRange(1, 0, n - 1, l, r, val);
    }

    // Point update: add val to arr[idx]
    // (Can be done via range update, or a dedicated function)
    void pointUpdate(int idx, long long val) {
        update(idx, idx, val);
    }

    // Range query: sum of elements in [l, r] (0-indexed)
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};

int main() {
    vector<int> arr = {2, 1, 5, 3, 4, 2};
    SegTree st(arr);

    cout << "Sum [0,5] = " << st.query(0, 5) << endl;  // 17
    cout << "Sum [1,4] = " << st.query(1, 4) << endl;  // 13

    st.update(1, 4, 3); // add 3 to [1,4]
    // Array is now [2, 4, 8, 6, 7, 2]

    cout << "After +3 to [1,4]:" << endl;
    cout << "Sum [0,5] = " << st.query(0, 5) << endl;  // 29
    cout << "Sum [1,4] = " << st.query(1, 4) << endl;  // 25
    cout << "Sum [3,3] = " << st.query(3, 3) << endl;  // 6

    return 0;
}

Segment Tree Without Lazy (Point Update Only)

If you only need point updates (no range updates), skip lazy propagation entirely. The code is much simpler:

CPP

class SegTree {
    int n;
    vector<long long> tree;

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) { tree[v] = a[tl]; return; }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

    void update(int v, int tl, int tr, int pos, long long val) {
        if (tl == tr) { tree[v] = val; return; }
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2*v, tl, tm, pos, val);
        else update(2*v+1, tm+1, tr, pos, val);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

    long long query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return tree[v];
        int tm = (tl + tr) / 2;
        return query(2*v, tl, tm, l, r) + query(2*v+1, tm+1, tr, l, r);
    }

public:
    SegTree(vector<int>& a) : n(a.size()), tree(4 * n) { build(a, 1, 0, n-1); }
    void update(int pos, long long val) { update(1, 0, n-1, pos, val); }
    long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};

Min/Max Segment Tree

Change the merge function and identity element:

CPP

// For minimum:
// Merge: tree[v] = min(tree[2*v], tree[2*v+1])
// Identity (no overlap): return INT_MAX

class MinSegTree {
    int n;
    vector<int> tree;

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) { tree[v] = a[tl]; return; }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        tree[v] = min(tree[2*v], tree[2*v+1]);  // <-- merge = min
    }

    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) { tree[v] = val; return; }
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2*v, tl, tm, pos, val);
        else update(2*v+1, tm+1, tr, pos, val);
        tree[v] = min(tree[2*v], tree[2*v+1]);
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return INT_MAX;  // <-- identity for min
        if (l <= tl && tr <= r) return tree[v];
        int tm = (tl + tr) / 2;
        return min(query(2*v, tl, tm, l, r),
                   query(2*v+1, tm+1, tr, l, r));
    }

public:
    MinSegTree(vector<int>& a) : n(a.size()), tree(4 * n) { build(a, 1, 0, n-1); }
    void update(int pos, int val) { update(1, 0, n-1, pos, val); }
    int query(int l, int r) { return query(1, 0, n-1, l, r); }
};

For max: Replace min with max and INT_MAX with INT_MIN.

Segment Tree with Range Assignment (Set, not Add)

Instead of "add val to range", we "set all elements in range to val".

The lazy semantics change: lazy stores the value to assign, and pushdown replaces rather than adds.

CPP

class AssignSegTree {
    int n;
    vector<long long> tree;
    vector<long long> lazy;
    vector<bool> hasLazy; // need a flag since 0 is a valid assignment

    void pushDown(int node, int start, int end) {
        if (hasLazy[node]) {
            int mid = (start + end) / 2;
            apply(2 * node, start, mid, lazy[node]);
            apply(2 * node + 1, mid + 1, end, lazy[node]);
            hasLazy[node] = false;
        }
    }

    void apply(int node, int start, int end, long long val) {
        tree[node] = val * (end - start + 1);  // sum of range = val * length
        lazy[node] = val;
        hasLazy[node] = true;
    }

    void updateRange(int node, int start, int end, int l, int r, long long val) {
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            apply(node, start, end, 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];
    }

    long long queryRange(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        pushDown(node, start, end);
        int mid = (start + end) / 2;
        return queryRange(2 * node, start, mid, l, r) +
               queryRange(2 * node + 1, mid + 1, end, l, r);
    }

public:
    AssignSegTree(int n) : n(n), tree(4 * n, 0), lazy(4 * n, 0), hasLazy(4 * n, false) {}

    void assign(int l, int r, long long val) { updateRange(1, 0, n - 1, l, r, val); }
    long long query(int l, int r) { return queryRange(1, 0, n - 1, l, r); }
};

Generic Segment Tree Template

For competitive programming, a reusable template that works with any associative operation:

CPP

template<typename T, T identity, T (*merge)(T, T)>
class SegTree {
    int n;
    vector<T> tree;

    void build(vector<T>& a, int v, int tl, int tr) {
        if (tl == tr) { tree[v] = a[tl]; return; }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        tree[v] = merge(tree[2*v], tree[2*v+1]);
    }

    void update(int v, int tl, int tr, int pos, T val) {
        if (tl == tr) { tree[v] = val; return; }
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2*v, tl, tm, pos, val);
        else update(2*v+1, tm+1, tr, pos, val);
        tree[v] = merge(tree[2*v], tree[2*v+1]);
    }

    T query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return identity;
        if (l <= tl && tr <= r) return tree[v];
        int tm = (tl + tr) / 2;
        return merge(query(2*v, tl, tm, l, r), query(2*v+1, tm+1, tr, l, r));
    }

public:
    SegTree(vector<T>& a) : n(a.size()), tree(4 * n) { build(a, 1, 0, n-1); }
    void update(int pos, T val) { update(1, 0, n-1, pos, val); }
    T query(int l, int r) { return query(1, 0, n-1, l, r); }
};

// Usage examples:
int sumMerge(int a, int b) { return a + b; }
int minMerge(int a, int b) { return min(a, b); }
int maxMerge(int a, int b) { return max(a, b); }
int gcdMerge(int a, int b) { return __gcd(a, b); }

// SegTree<int, 0, sumMerge> sumTree(arr);
// SegTree<int, INT_MAX, minMerge> minTree(arr);
// SegTree<int, INT_MIN, maxMerge> maxTree(arr);
// SegTree<int, 0, gcdMerge> gcdTree(arr);

Iterative Segment Tree (Bottom-Up)

For simple operations (point update + range query without lazy), an iterative implementation is faster due to no recursion overhead:

CPP

class IterativeSegTree {
    int n;
    vector<long long> tree;

public:
    IterativeSegTree(vector<int>& arr) : n(arr.size()), tree(2 * n) {
        // Build: copy array to leaves, then compute parents
        for (int i = 0; i < n; i++) tree[n + i] = arr[i];
        for (int i = n - 1; i > 0; i--) tree[i] = tree[2*i] + tree[2*i+1];
    }

    // Point update: set position p to value val (0-indexed)
    void update(int p, long long val) {
        tree[p + n] = val;
        for (int i = (p + n) / 2; i >= 1; i /= 2)
            tree[i] = tree[2*i] + tree[2*i+1];
    }

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

How the iterative query works:

Query [2, 5] (0-indexed):
  l = 2 + 8 = 10, r = 5 + 8 + 1 = 14

  Iteration 1: l=10, r=14
    l is even -> skip
    r is even -> r-- = 13, add tree[13]
    l = 5, r = 7

  Iteration 2: l=5, r=7
    l is odd -> add tree[5], l++ = 6
    r is odd -> r-- = 6, add tree[6]
    l = 3, r = 3

  l == r -> stop

  Result = tree[13] + tree[5] + tree[6]
  These three nodes exactly cover [2, 5]. Beautiful!

This iterative version uses only 2*n memory (not 4*n) and has smaller constants.

Persistent Segment Tree (Brief Overview)

Idea: When we update the tree, instead of modifying nodes in-place, we create new nodes for the modified path and share all unchanged nodes with the old version. This gives us access to every historical version of the tree.

Space: O(n) for initial build + O(log n) per update (one new node per level). Time: Same as regular segment tree.

Application: k-th smallest element in a range, versioned data structures.

CPP

struct Node {
    int left, right; // indices into node pool
    long long val;
};

vector<Node> nodes;
vector<int> roots; // root of each version

int newNode(long long val = 0, int left = 0, int right = 0) {
    nodes.push_back({left, right, val});
    return nodes.size() - 1;
}

int build(vector<int>& a, int tl, int tr) {
    if (tl == tr) return newNode(a[tl]);
    int tm = (tl + tr) / 2;
    int l = build(a, tl, tm);
    int r = build(a, tm+1, tr);
    return newNode(nodes[l].val + nodes[r].val, l, r);
}

int update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) return newNode(val);
    int tm = (tl + tr) / 2;
    int l = nodes[v].left, r = nodes[v].right;
    if (pos <= tm)
        l = update(l, tl, tm, pos, val);
    else
        r = update(r, tm+1, tr, pos, val);
    return newNode(nodes[l].val + nodes[r].val, l, r);
}

long long query(int v, int tl, int tr, int ql, int qr) {
    if (ql > tr || qr < tl) return 0;
    if (ql <= tl && tr <= qr) return nodes[v].val;
    int tm = (tl + tr) / 2;
    return query(nodes[v].left, tl, tm, ql, qr) +
           query(nodes[v].right, tm+1, tr, ql, qr);
}

Merge Sort Tree (Segment Tree with Sorted Lists)

Each node stores a sorted list of elements in its range. Enables queries like "count of elements in [l, r] that are less than k" in O(log^2 n).

CPP

class MergeSortTree {
    int n;
    vector<vector<int>> tree;

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) { tree[v] = {a[tl]}; return; }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        merge(tree[2*v].begin(), tree[2*v].end(),
              tree[2*v+1].begin(), tree[2*v+1].end(),
              back_inserter(tree[v]));
    }

    // Count elements < k in range [l, r]
    int query(int v, int tl, int tr, int l, int r, int k) {
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r)
            return lower_bound(tree[v].begin(), tree[v].end(), k) - tree[v].begin();
        int tm = (tl + tr) / 2;
        return query(2*v, tl, tm, l, r, k) + query(2*v+1, tm+1, tr, l, r, k);
    }

public:
    MergeSortTree(vector<int>& a) : n(a.size()), tree(4 * n) { build(a, 1, 0, n-1); }
    int countLess(int l, int r, int k) { return query(1, 0, n-1, l, r, k); }
};

Build: O(n log n). Query: O(log^2 n). Space: O(n log n).

Classic Problems

1. Range Sum Query - Mutable (LeetCode 307)

CPP

class NumArray {
    int n;
    vector<int> tree;

    void build(vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) { tree[v] = a[tl]; return; }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) { tree[v] = val; return; }
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2*v, tl, tm, pos, val);
        else update(2*v+1, tm+1, tr, pos, val);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return tree[v];
        int tm = (tl + tr) / 2;
        return query(2*v, tl, tm, l, r) + query(2*v+1, tm+1, tr, l, r);
    }

public:
    NumArray(vector<int>& nums) : n(nums.size()), tree(4 * n) {
        if (n > 0) build(nums, 1, 0, n - 1);
    }

    void update(int index, int val) {
        update(1, 0, n - 1, index, val);
    }

    int sumRange(int left, int right) {
        return query(1, 0, n - 1, left, right);
    }
};

2. Count of Range Sum (LeetCode 327)

Problem: Given an array and bounds [lower, upper], count the number of range sums sum(i, j) that lie in [lower, upper].

Approach: Compute prefix sums. For each prefix sum p[j], count previous prefix sums p[i] where lower <= p[j] - p[i] <= upper, i.e., p[j] - upper <= p[i] <= p[j] - lower. Use a segment tree (or BIT) with coordinate compression.

CPP

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        vector<long long> prefix(n + 1);
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

        // Coordinate compression
        vector<long long> sorted_vals = prefix;
        sort(sorted_vals.begin(), sorted_vals.end());
        sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()), sorted_vals.end());
        int m = sorted_vals.size();

        auto getIdx = [&](long long val) {
            return lower_bound(sorted_vals.begin(), sorted_vals.end(), val) - sorted_vals.begin();
        };

        // BIT for counting
        vector<int> bit(m + 1, 0);
        auto update = [&](int i) { for (i++; i <= m; i += i & (-i)) bit[i]++; };
        auto query = [&](int i) -> int {
            int s = 0; for (i++; i > 0; i -= i & (-i)) s += bit[i]; return s;
        };
        auto rangeQuery = [&](int l, int r) -> int {
            if (l > r) return 0;
            return query(r) - (l > 0 ? query(l - 1) : 0);
        };

        int count = 0;
        for (int j = 0; j <= n; j++) {
            // Count prefix[i] in [prefix[j] - upper, prefix[j] - lower] for i < j
            if (j > 0) {
                long long lo = prefix[j] - upper;
                long long hi = prefix[j] - lower;
                int li = getIdx(lo);
                int ri = (int)(upper_bound(sorted_vals.begin(), sorted_vals.end(), hi)
                               - sorted_vals.begin()) - 1;
                if (li <= ri) count += rangeQuery(li, ri);
            }
            update(getIdx(prefix[j]));
        }
        return count;
    }
};

3. My Calendar II (LeetCode 731)

Problem: Implement a calendar where you can add events. An event can overlap with at most one other event (no triple booking). Return false if adding causes a triple booking.

Approach: Use a lazy segment tree over the time range. Each event adds +1 to its range. Before adding, check if the max value in the range is already >= 2.

CPP

class MyCalendarTwo {
    // Segment tree with lazy propagation for range add + range max query
    // Using a dynamic (map-based) approach since the range can be huge
    map<int, int> tree, lazy;

    void pushDown(int node) {
        if (lazy.count(node) && lazy[node] != 0) {
            tree[2*node] += lazy[node];
            tree[2*node+1] += lazy[node];
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
            lazy[node] = 0;
        }
    }

    void update(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;
            lazy[node] += val;
            return;
        }
        pushDown(node);
        int mid = (start + end) / 2;
        update(2*node, start, mid, l, r, val);
        update(2*node+1, mid+1, end, l, r, val);
        tree[node] = max(tree[2*node], tree[2*node+1]);
    }

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

    static const int MAXVAL = 1000000000;

public:
    bool book(int start, int end) {
        end--; // make inclusive
        if (query(1, 0, MAXVAL, start, end) >= 2) return false;
        update(1, 0, MAXVAL, start, end, 1);
        return true;
    }
};

Note: Using a map for nodes makes this a "dynamic segment tree" that only allocates nodes as needed. For competitive programming, this avoids pre-allocating huge arrays.

4. Falling Squares (LeetCode 699)

Problem: Squares are dropped onto the x-axis. Each square lands on the highest surface below it. After each drop, report the overall maximum height.

Approach: Coordinate compress the x-coordinates. Use a lazy segment tree for range max query and range assignment.

CPP

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        // Coordinate compression
        vector<int> coords;
        for (auto& p : positions) {
            coords.push_back(p[0]);
            coords.push_back(p[0] + p[1] - 1);
        }
        sort(coords.begin(), coords.end());
        coords.erase(unique(coords.begin(), coords.end()), coords.end());
        int m = coords.size();

        auto getIdx = [&](int x) {
            return lower_bound(coords.begin(), coords.end(), x) - coords.begin();
        };

        // Segment tree: range max query, range assignment update
        vector<int> tree(4 * m, 0), lazy(4 * m, 0);
        vector<bool> hasLazy(4 * m, false);

        function<void(int, int, int)> push = [&](int v, int tl, int tr) {
            if (hasLazy[v]) {
                tree[v] = max(tree[v], lazy[v]);
                if (tl != tr) {
                    lazy[2*v] = max(lazy[2*v], lazy[v]); hasLazy[2*v] = true;
                    lazy[2*v+1] = max(lazy[2*v+1], lazy[v]); hasLazy[2*v+1] = true;
                }
                hasLazy[v] = false; lazy[v] = 0;
            }
        };

        function<int(int, int, int, int, int)> query = [&](int v, int tl, int tr, int l, int r) -> int {
            push(v, tl, tr);
            if (l > tr || r < tl) return 0;
            if (l <= tl && tr <= r) return tree[v];
            int tm = (tl + tr) / 2;
            return max(query(2*v, tl, tm, l, r), query(2*v+1, tm+1, tr, l, r));
        };

        function<void(int, int, int, int, int, int)> update = [&](int v, int tl, int tr, int l, int r, int val) {
            push(v, tl, tr);
            if (l > tr || r < tl) return;
            if (l <= tl && tr <= r) {
                lazy[v] = val; hasLazy[v] = true;
                push(v, tl, tr);
                return;
            }
            int tm = (tl + tr) / 2;
            update(2*v, tl, tm, l, r, val);
            update(2*v+1, tm+1, tr, l, r, val);
            tree[v] = max(tree[2*v], tree[2*v+1]);
        };

        vector<int> result;
        int overallMax = 0;
        for (auto& p : positions) {
            int l = getIdx(p[0]);
            int r = getIdx(p[0] + p[1] - 1);
            int curMax = query(1, 0, m-1, l, r);
            int newH = curMax + p[1];
            update(1, 0, m-1, l, r, newH);
            overallMax = max(overallMax, newH);
            result.push_back(overallMax);
        }
        return result;
    }
};

5. Rectangle Area II (LeetCode 850)

Problem: Given a list of axis-aligned rectangles, find the total area covered (counting overlapping areas only once).

Approach: Line sweep + segment tree to track the length of covered intervals on the y-axis.

CPP

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int MOD = 1e9 + 7;

        // Collect y-coordinates for compression
        vector<int> ys;
        for (auto& r : rectangles) {
            ys.push_back(r[1]);
            ys.push_back(r[3]);
        }
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        int m = ys.size();

        auto getIdx = [&](int y) {
            return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
        };

        // Events: (x, type, y1_idx, y2_idx)
        // type: +1 for left edge, -1 for right edge
        vector<array<int, 4>> events;
        for (auto& r : rectangles) {
            int y1 = getIdx(r[1]), y2 = getIdx(r[3]);
            events.push_back({r[0], 1, y1, y2});
            events.push_back({r[2], -1, y1, y2});
        }
        sort(events.begin(), events.end());

        // Segment tree: count[v] = number of full covers, len[v] = total covered length
        vector<int> cnt(4 * m, 0);
        vector<long long> len(4 * m, 0);

        function<void(int, int, int)> pushUp = [&](int v, int tl, int tr) {
            if (cnt[v] > 0) {
                len[v] = ys[tr + 1] - ys[tl]; // note: tr+1 to get actual y-coordinate range
            } else if (tl == tr) {
                len[v] = 0;
            } else {
                len[v] = len[2*v] + len[2*v+1];
            }
        };

        function<void(int, int, int, int, int, int)> update = [&](int v, int tl, int tr, int l, int r, int val) {
            if (l > tr || r < tl || l > r) return;
            if (l <= tl && tr <= r) {
                cnt[v] += val;
                pushUp(v, tl, tr);
                return;
            }
            int tm = (tl + tr) / 2;
            update(2*v, tl, tm, l, r, val);
            update(2*v+1, tm+1, tr, l, r, val);
            pushUp(v, tl, tr);
        };

        long long totalArea = 0;
        int prevX = events[0][0];
        for (auto& e : events) {
            int x = e[0], type = e[1], y1 = e[2], y2 = e[3];
            totalArea = (totalArea + len[1] % MOD * ((x - prevX) % MOD)) % MOD;
            prevX = x;
            update(1, 0, m - 2, y1, y2 - 1, type); // update y-interval [y1, y2-1]
        }
        return totalArea;
    }
};

Segment Tree vs BIT vs Sparse Table

Decision Guide

Use Segment Tree when:

You need range updates AND range queries (lazy propagation)
You need min/max/GCD or other non-invertible operations WITH updates
You need persistent/versioned queries
The problem requires complex merge operations (e.g., count + sum together)

Use BIT (Fenwick Tree) when:

You only need point update + prefix/range sum (or other invertible operation)
You want the simplest possible code
Memory is tight (BIT uses n+1 vs 4n for segment tree)
Speed matters (BIT has smaller constant factors)

Use Sparse Table when:

The array is static (no updates at all)
You need O(1) range minimum/maximum queries
You're doing offline processing

Common Pitfalls

Array size: Always allocate 4*n for the segment tree array. 2*n is not enough when n is not a power of 2.
0-indexed vs 1-indexed: Be consistent. The tree nodes are 1-indexed (root = 1). The array can be 0 or 1-indexed, but make sure build/query/update match.
Lazy propagation order: Always pushDown before accessing children. Forgetting this leads to subtle bugs that are hard to debug.
Identity element: Must be correct for your operation:
- Sum: 0
- Min: INT_MAX (or LLONG_MAX)
- Max: INT_MIN (or LLONG_MIN)
- GCD: 0 (since gcd(0, x) = x)
- Product: 1
- Bitwise OR: 0
- Bitwise AND: all-ones (~0)
Overflow: For sum queries on large arrays with large values, use long long.
Lazy with assignment vs addition: Assignment lazy must replace children's lazy values. Addition lazy accumulates. Mixing them up causes wrong answers.

Summary

The segment tree is arguably the most versatile range query data structure. Its recursive divide-and-conquer structure naturally supports any associative merge operation, and lazy propagation extends it to handle range updates efficiently. The key ideas are:

Divide the array into a binary tree of ranges -- each node owns a contiguous subarray.
Merge children to compute parents -- bottom-up build, bottom-up update.
Three-way case analysis for queries -- total overlap (return), no overlap (skip), partial overlap (recurse).
Lazy propagation -- defer updates, push down only when needed.

Master these four ideas and you can solve virtually any range query problem.