Chapter 3.9: Introduction to Segment Trees

📝 Before You Continue: You should understand prefix sums (Chapter 3.2), arrays, and recursion (Chapter 2.3). Segment trees are a more advanced data structure — make sure you're comfortable with recursion before diving in.

Segment trees are one of the most powerful data structures in competitive programming. They solve a fundamental problem that prefix sums cannot: range queries with updates.

3.9.1 The Problem: Why We Need Segment Trees

Consider this challenge:

• Array A of N integers
• Q1: What is the sum of A[l..r]? (Range sum query)
• Q2: Update A[i] = x (Point update)

Prefix sum solution: Range query in O(1), but update requires O(N) to recompute all prefix sums. For M mixed queries, total: O(NM) — too slow for N,M = 10^5.

Segment tree solution: Both query and update in O(log N). For M mixed queries: O(M log N) ✓

The diagram shows a segment tree built on array [1, 3, 5, 7, 9, 11]. Each internal node stores the sum of its range. A query for range [2,4] (sum=21) is answered by combining just 2 nodes — O(log N) instead of O(N).

3.9.2 Structure: What Is a Segment Tree?

A segment tree is a complete binary tree where:

• Each leaf corresponds to a single array element
• Each internal node stores the aggregate (sum, min, max, etc.) of its range
• The root covers the entire array [0..N-1]
• A node covering [l..r] has two children: [l..mid] and [mid+1..r]

For an array of N elements, the tree has at most 4N nodes (we use a 1-indexed tree array of size 4N as a safe upper bound).

Array: [1, 3, 5, 7, 9, 11]  (indices 0..5)

Tree (1-indexed, node i has children 2i and 2i+1):
         [0..5]=36
        /          \
  [0..2]=9       [3..5]=27
   /     \        /      \
[0..1]=4 [2]=5  [3..4]=16  [5]=11
  /   \          /    \
[0]=1 [1]=3   [3]=7  [4]=9

下图展示了线段树的完整结构，以及查询 sum([2,4]) 时蓝色高亮的访问路径：

3.9.3 Building the Segment Tree

// Solution: Segment Tree Build — O(N)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int tree[4 * MAXN];  // segment tree array (4x array size for safety)
int arr[MAXN];       // original array

// Build: recursively fill tree[]
// node = current tree node index (start with 1)
// start, end = range this node covers
void build(int node, int start, int end) {
    if (start == end) {
        // Leaf node: stores the array element
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        // Build left and right children first
        build(2 * node, start, mid);        // left child
        build(2 * node + 1, mid + 1, end);  // right child
        // Internal node: sum of children
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1);  // build from node 1, covering [0..n-1]

    return 0;
}

Build trace for [1, 3, 5, 7, 9, 11]:

build(1, 0, 5):
  build(2, 0, 2):
    build(4, 0, 1):
      build(8, 0, 0): tree[8] = arr[0] = 1
      build(9, 1, 1): tree[9] = arr[1] = 3
      tree[4] = tree[8] + tree[9] = 4
    build(5, 2, 2): tree[5] = arr[2] = 5
    tree[2] = tree[4] + tree[5] = 9
  build(3, 3, 5):
    build(6, 3, 4):
      ...
    tree[3] = 27
  tree[1] = 9 + 27 = 36

3.9.4 Range Query

Query sum of arr[l..r]:

Key idea: Recursively descend the tree. At each node covering [start..end]:

• If [start..end] is completely inside [l..r]: return this node's value (done!)
• If [start..end] is completely outside [l..r]: return 0 (no contribution)
• Otherwise: recurse into both children, sum the results

// Range Query: sum of arr[l..r] — O(log N)
// node = current tree node, [start, end] = range it covers
// [l, r] = query range
int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        // Case 1: Current segment completely outside query range
        return 0;   // identity for sum (use INT_MAX for min queries)
    }
    if (l <= start && end <= r) {
        // Case 2: Current segment completely inside query range
        return tree[node];   // ← KEY LINE: use this node directly!
    }
    // Case 3: Partial overlap — recurse into children
    int mid = (start + end) / 2;
    int leftSum  = query(2 * node, start, mid, l, r);
    int rightSum = query(2 * node + 1, mid + 1, end, l, r);
    return leftSum + rightSum;
}

// Usage: sum of arr[2..4]
int result = query(1, 0, n - 1, 2, 4);
cout << result << "\n";  // 5 + 7 + 9 = 21

Query trace for [2..4] on tree of [1,3,5,7,9,11]:

query(1, 0, 5, 2, 4):
  query(2, 0, 2, 2, 4): [0..2] partially overlaps [2..4]
    query(4, 0, 1, 2, 4): [0..1] outside [2..4] → return 0
    query(5, 2, 2, 2, 4): [2..2] inside [2..4] → return 5
    return 0 + 5 = 5
  query(3, 3, 5, 2, 4): [3..5] partially overlaps [2..4]
    query(6, 3, 4, 2, 4): [3..4] inside [2..4] → return 16
    query(7, 5, 5, 2, 4): [5..5] outside [2..4] → return 0
    return 16 + 0 = 16
  return 5 + 16 = 21 ✓

Only 4 nodes visited — O(log N)!

3.9.5 Point Update

Update arr[i] = x (change a single element):

// Point Update: set arr[idx] = val — O(log N)
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // Leaf: update the value
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);      // update in left child
        } else {
            update(2 * node + 1, mid + 1, end, idx, val); // update in right child
        }
        // Update this internal node after child changes
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

// Usage: set arr[2] = 10
update(1, 0, n - 1, 2, 10);

3.9.6 Complete Implementation

Here's the full, contest-ready segment tree:

// Solution: Segment Tree — O(N) build, O(log N) query/update
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long tree[4 * MAXN];

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

long long 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];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r)
         + query(2 * node + 1, mid + 1, end, l, r);
}

void update(int node, int start, int end, int idx, long long val) {
    if (start == end) {
        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];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    long long arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1, arr);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Point update: set arr[i] = v
            int i; long long v;
            cin >> i >> v;
            update(1, 0, n - 1, i, v);
        } else {
            // Range query: sum of arr[l..r]
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

Sample Input:

6 5
1 3 5 7 9 11
2 2 4
1 2 10
2 2 4
2 0 5
1 0 0

Sample Output:

21
26
41

(第1次查询 [2,4] = 5+7+9 = 21；执行 update arr[2]=10 后，第2次查询 [2,4] = 10+7+9 = 26；第3次查询 [0,5] = 1+3+10+7+9+11 = 41；最后一条操作 update arr[0]=0 无输出)

3.9.7 Segment Tree vs. Fenwick Tree (BIT)

💡 Key Insight: If you need range sum with updates, a Fenwick tree is simpler. If you need range minimum, range maximum, or any other aggregate that isn't a prefix operation, use a segment tree.

3.9.8 Range Minimum Query Variant

Just change the aggregate from + to min:

// Range Minimum Segment Tree — same structure, different operation
void build_min(int node, int start, int end, int arr[]) {
    if (start == end) { tree[node] = arr[start]; return; }
    int mid = (start + end) / 2;
    build_min(2*node, start, mid, arr);
    build_min(2*node+1, mid+1, end, arr);
    tree[node] = min(tree[2*node], tree[2*node+1]);  // ← changed to min
}

int query_min(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return INT_MAX;   // ← identity for min
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return min(query_min(2*node, start, mid, l, r),
               query_min(2*node+1, mid+1, end, l, r));
}

⚠️ Common Mistakes

1. Array size too small: Always allocate tree[4 * MAXN]. Using 2 * MAXN will cause out-of-bounds for non-power-of-2 sizes.
2. Wrong identity for out-of-range: For sum queries, return 0. For min queries, return INT_MAX. For max queries, return INT_MIN.
3. Forgetting to update the parent node: After updating a child, you MUST recompute the parent: tree[node] = tree[2*node] + tree[2*node+1].
4. 0-indexed vs 1-indexed confusion: This implementation uses 0-indexed arrays but 1-indexed tree nodes. Be consistent.
5. Using segment tree when prefix sum suffices: If there are no updates, prefix sum (O(1) query) beats segment tree (O(log N) query). Use the simpler tool when appropriate.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: When to choose segment tree vs prefix sum?

A: Simple rule — if the array never changes, prefix sum is better (O(1) query vs O(log N)). If the array gets modified (point updates), use segment tree or BIT. If you need range updates (add a value to a range), use segment tree with lazy propagation.

Q2: Why does the tree array need size 4N?

A: A segment tree is a complete binary tree. When N is not a power of 2, the last level may be incomplete but still needs space. In the worst case, about 4N nodes are needed. Using 4*MAXN is a safe upper bound.

Q3: Which is better, Fenwick Tree (BIT) or Segment Tree?

A: BIT code is shorter (~15 lines vs 30 lines), has smaller constants, but can only handle "prefix-decomposable" operations (like sum). Segment Tree is more general (can do range min/max, GCD, etc.) and supports more complex operations (like lazy propagation). In contests: use BIT when possible, switch to Segment Tree when BIT is insufficient.

Q4: What types of queries can segment trees handle?

A: Any operation satisfying the associative law: sum (+), minimum (min), maximum (max), GCD, XOR, product, etc. The key is having an "identity element" (e.g., 0 for sum, INT_MAX for min, INT_MIN for max).

Q5: What is Lazy Propagation? When is it needed?

A: When you need to "add V to every element in range [L,R]" (range update), the naive approach updates every leaf from L to R (O(N)), which is too slow. Lazy Propagation stores updates "lazily" in internal nodes and only pushes them down when a child node actually needs to be queried, optimizing range updates to O(log N) as well.

🔗 Connections to Later Chapters

• Chapter 3.2 (Prefix Sums): the "simplified version" of segment trees — use prefix sums when there are no update operations
• Chapters 5.1–5.2 (Graphs): Euler Tour + segment tree can efficiently handle path queries on trees
• Chapters 6.1–6.3 (DP): some DP optimizations require segment trees to maintain range min/max of DP values
• Segment tree is a core data structure at USACO Gold level, mastering it solves a large number of Gold problems

Practice Problems

Problem 3.9.1 — Classic Range Sum 🟢 Easy Implement a segment tree. Handle N elements and Q queries: either update a single element or query the sum of a range.

Problem 3.9.2 — Range Minimum 🟡 Medium Same as above but query the minimum of a range. Handle point updates.

Problem 3.9.3 — Number of Inversions 🔴 Hard Count the number of pairs (i,j) where i < j and arr[i] > arr[j].

🏆 Challenge: USACO 2016 February Gold: Fencing the Cows A problem requiring range max queries with updates. Try solving it with both a Fenwick tree and a segment tree to understand the tradeoffs.

3.9.6 Lazy Propagation — Range Updates in O(log N)

The segment tree so far handles point updates (change one element). But what about range updates: "add V to all elements in [L, R]"?

Without lazy propagation, we'd need O(N) updates (one per element). With lazy propagation, we achieve O(log N) range updates.

💡 Key Insight: Instead of immediately updating all affected leaf nodes, we "lazily" defer the update — store it at the highest applicable node and only push it down when we actually need the children.

How Lazy Propagation Works

Each node now stores two values:

• tree[node]: the actual aggregated value (range sum) for this range
• lazy[node]: a pending update that hasn't been pushed to children yet

The push-down rule: When we visit a node with a pending lazy update, we:

1. Apply the lazy update to the node's value
2. Pass the lazy update to both children (push down)
3. Clear the lazy for this node

Example: Array = [1, 2, 3, 4, 5], update "add 10 to [1..3]"

Initial tree:
         [15]            ← sum of [0..4]
        /      \
     [6]        [9]      ← sum of [0..2], [3..4]
    /   \      /   \
  [3]  [3]  [4]   [5]   ← sum of [0..1], [2], [3], [4]
  / \
 [1] [2]

After update "add 10 to [1..3]" with lazy propagation:
We need to update indices 1, 2, 3 (0-indexed).

At node covering [0..2]:
  - Only partially inside [1..3], so recurse down
  
At node covering [0..1]:
  - Partially inside [1..3], so recurse down
  - At leaf [1]: update arr[1] += 10. tree = [1, 12, 3, 4, 5]
  
At leaf [2]:
  - Fully inside [1..3]: store lazy, don't recurse!
  - lazy[covering [2]] = +10
  - tree[node] += 10 × (length of [2]) = +10
  
At node covering [3..4]:
  - Partially inside, recurse to [3]
  - Leaf [3]: += 10

Complete Lazy Propagation Implementation

// Solution: Segment Tree with Lazy Propagation
// Supports: range add update, range sum query — O(log N) each
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

ll tree[4 * MAXN];   // tree[node] = sum of range
ll lazy[4 * MAXN];   // lazy[node] = pending add value (0 means no pending)

// ── PUSH DOWN: apply pending lazy to children ──
// Called before we recurse into children
void pushDown(int node, int start, int end) {
    if (lazy[node] == 0) return;  // no pending update, nothing to do
    
    int mid = (start + end) / 2;
    int left = 2 * node, right = 2 * node + 1;
    
    // Update left child's sum: add lazy * (number of elements in left child)
    tree[left]  += lazy[node] * (mid - start + 1);
    tree[right] += lazy[node] * (end - mid);
    
    // Pass lazy to children
    lazy[left]  += lazy[node];
    lazy[right] += lazy[node];
    
    // Clear current node's lazy (it's been pushed down)
    lazy[node] = 0;
}

// ── BUILD: construct tree from array ──
void build(int node, int start, int end, ll arr[]) {
    lazy[node] = 0;  // no pending updates initially
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2*node, start, mid, arr);
    build(2*node+1, mid+1, end, arr);
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── RANGE UPDATE: add val to all elements in [l, r] ──
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;  // out of range: no-op
    
    if (l <= start && end <= r) {
        // Current segment fully inside [l, r]: apply lazy here, don't recurse
        tree[node] += val * (end - start + 1);  // ← KEY: multiply by range length
        lazy[node] += val;                        // store pending for children
        return;
    }
    
    // Partial overlap: push down existing lazy, then recurse
    pushDown(node, start, end);  // ← CRITICAL: push before recursing!
    
    int mid = (start + end) / 2;
    update(2*node,   start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);
    
    // Update current node from children
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── RANGE QUERY: sum of elements in [l, r] ──
ll 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: return stored sum (already includes lazy!)
    }
    
    // Partial overlap: push down, then recurse
    pushDown(node, start, end);  // ← CRITICAL: push before recursing!
    
    int mid = (start + end) / 2;
    ll leftSum  = query(2*node,   start, mid, l, r);
    ll rightSum = query(2*node+1, mid+1, end, l, r);
    return leftSum + rightSum;
}

// ── COMPLETE EXAMPLE ──
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    
    ll arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    build(1, 0, n-1, arr);
    
    while (q--) {
        int type;
        cin >> type;
        
        if (type == 1) {
            // Range update: add val to [l, r]
            int l, r; ll val;
            cin >> l >> r >> val;
            update(1, 0, n-1, l, r, val);
        } else {
            // Range query: sum of [l, r]
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n-1, l, r) << "\n";
        }
    }
    
    return 0;
}

Visual Trace: Range Update with Lazy

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

Initial tree (sums):
tree[1]  = 21  [0..5]
tree[2]  =  6  [0..2]    tree[3]  = 15  [3..5]
tree[4]  =  3  [0..1]    tree[5]  =  3  [2..2]    tree[6]  =  7  [3..4]    tree[7]  =  6  [5..5]
tree[8]  =  1  [0..0]    tree[9]  =  2  [1..1]   tree[12]  =  4  [3..3]   tree[13]  =  3  [4..4]

update(1, 0, 5, 1, 4, +10):  (add 10 to indices 1..4)

  At node 1 [0..5]: partial overlap, pushDown(1)—no lazy. Recurse.
    At node 2 [0..2]: partial overlap, pushDown(2)—no lazy. Recurse.
      At node 4 [0..1]: partial overlap, pushDown(4)—no lazy. Recurse.
        At node 8 [0..0]: outside [1..4]. Return.
        At node 9 [1..1]: FULLY inside [1..4].
          tree[9] += 10×1 = 12. lazy[9] = 10. Return.
      tree[4] = tree[8] + tree[9] = 1 + 12 = 13.
      At node 5 [2..2]: FULLY inside [1..4].
        tree[5] += 10×1 = 13. lazy[5] = 10. Return.
    tree[2] = 13 + 13 = 26.
    At node 3 [3..5]: partial overlap. pushDown(3)—no lazy. Recurse.
      At node 6 [3..4]: FULLY inside [1..4].
        tree[6] += 10×2 = 27. lazy[6] = 10. Return.   ← lazy stored for later!
      At node 7 [5..5]: outside [1..4]. Return.
    tree[3] = 27 + 6 = 33.
  tree[1] = 26 + 33 = 59. ✓ (original 21 + 10×4 = 61... let me recheck)

query(1, 0, 5, 2, 3): sum of [2..3]
  At node 1 [0..5]: partial. pushDown(1)—no lazy. Recurse.
  At node 2 [0..2]: partial. pushDown(2)—no lazy. Recurse.
    At node 4 [0..1]: outside [2..3]. Return 0.
    At node 5 [2..2]: FULLY inside. Return tree[5] = 13. ✓ (arr[2] = 3+10 = 13)
  At node 3 [3..5]: partial. pushDown(3)—no lazy. Recurse.
    At node 6 [3..4]: partial. pushDown(6)! (lazy[6] = 10)
      tree[12] += 10×1 = 14, lazy[12] = 10.
      tree[13] += 10×1 = 13, lazy[13] = 10.
      lazy[6] = 0.
      At node 12 [3..3]: FULLY inside. Return tree[12] = 14. ✓ (arr[3] = 4+10 = 14)
      At node 13 [4..4]: outside. Return 0.
  Result = 13 + 14 = 27. ✓

Complexity Analysis

Why O(log N)? Each update/query visits at most O(log N) "fully covered" nodes (where we stop and apply lazy). Between two consecutive fully-covered nodes at the same level, there's at most one partially-covered node that requires descent.

⚠️ Lazy Propagation Common Mistakes

// BAD: This gives wrong answers!
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;
    if (l <= start && end <= r) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    // FORGOT: pushDown(node, start, end); ← BUG!
    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] = tree[2*node] + tree[2*node+1];
}

// GOOD: Push pending lazy before going to children
void update(int node, int start, int end, int l, int r, ll 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);  // ← ALWAYS before recursing!
    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] = tree[2*node] + tree[2*node+1];
}

Top 4 Lazy Propagation Bugs:

1. Forgetting pushDown before recursion — children receive parent's lazy on top of their own, giving wrong query results
2. Wrong size multiplier — tree[node] += val instead of tree[node] += val * (end - start + 1). The node stores a SUM, so adding val to each of (end-start+1) elements means adding val*(size) to the sum.
3. Not initializing lazy[] to 0 — use memset(lazy, 0, sizeof(lazy)) or initialize in build()
4. Mixing lazy for different operations — if you have both "range add" and "range multiply" lazy, the order matters. You need two separate lazy arrays and a careful push-down combining both.

Generalizing Lazy Propagation

The pattern works for any operation where:

• The aggregate is an associative operation (sum, min, max, XOR...)
• The update distributes over the aggregate (sum += k*n when adding k to n elements)

Common variants: