Skip to main content

​
Segment Trees

Segment Tree Structure

​
Why Segment Trees?

Segment trees answer range queries and handle point/range updates in O(log n) time. They’re essential for problems involving:
  • Range sum/min/max/GCD queries
  • Range updates (add/set all elements)
  • Count elements in range satisfying condition
Pattern Recognition Signals:
  • “Query sum/min/max from L to R” → Segment tree
  • “Update element at position i” → Segment tree with point update
  • “Add x to all elements from L to R” → Lazy propagation
  • “Count elements > k in range” → Merge sort tree or segment tree with sets

​
Basic Segment Tree (Point Update, Range Query)

class SegTree {
public:
    int n;
    vector<long long> tree;
    
    SegTree(int n) : n(n), tree(4 * n, 0) {}
    
    SegTree(vector<int>& arr) : n(arr.size()), tree(4 * n) {
        build(arr, 1, 0, n - 1);
    }
    
    void build(vector<int>& arr, int node, int start, int end) {
        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];  // Combine
    }
    
    void update(int idx, int val) {
        update(1, 0, n - 1, idx, val);
    }
    
    void update(int node, int start, int end, int idx, int 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];
    }
    
    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
    
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;  // Out of range (identity for sum)
        }
        
        if (l <= start && end <= r) {
            return tree[node];  // Fully contained
        }
        
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, l, r) +
               query(2 * node + 1, mid + 1, end, l, r);
    }
};

​
Usage

vector<int> arr = {1, 3, 5, 7, 9, 11};
SegTree st(arr);

cout << st.query(1, 3);  // 15 (3 + 5 + 7)
st.update(2, 10);        // arr[2] = 10
cout << st.query(1, 3);  // 20 (3 + 10 + 7)

​
Segment Tree for Different Operations

Change the combine function and identity element. 
// Range Minimum Query
long long combine(long long a, long long b) {
    return min(a, b);
}
long long identity = LLONG_MAX;

// Range Maximum Query
long long combine(long long a, long long b) {
    return max(a, b);
}
long long identity = LLONG_MIN;

// Range GCD Query
long long combine(long long a, long long b) {
    return __gcd(a, b);
}
long long identity = 0;

// Range XOR Query
long long combine(long long a, long long b) {
    return a ^ b;
}
long long identity = 0;

​
Lazy Propagation (Range Updates)

When you need to update a range of elements, not just one. The Problem: Adding a value to all elements in range [L, R] would require O(R - L + 1) point updates, making it O(n) per update—too slow! The Insight: Don’t update immediately. Instead, store a “pending update” (lazy value) at a node. Only push it down to children when needed. How it works:
  1. Range Update: When updating [L, R], if a node’s range is completely inside [L, R], mark it with a lazy value and return (don’t recurse)
  2. Push Down: Before accessing children, push the lazy value down to them
  3. Query: Same as before, but push down lazy values as you traverse
Visual Example - Adding 5 to [1, 4] in array [1, 2, 3, 4, 5, 6]: 
Before:                    After marking lazy=5:
       21                         21 + 5*4 = 41
      /  \                            /    \
    10    11                   10+5*2=20   11
   /  \   / \                    lazy=5    / \
  3   7  9  11                            9   11
 / \ / \                                 (children not updated yet)
1 2 3 4
The lazy value is only pushed down when we need to access children. 
class LazySegTree {
public:
    int n;
    vector<long long> tree, lazy;
    
    LazySegTree(int n) : n(n), tree(4 * n, 0), lazy(4 * n, 0) {}
    
    void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            
            // Push lazy value to children
            tree[2 * node] += lazy[node] * (mid - start + 1);
            tree[2 * node + 1] += lazy[node] * (end - mid);
            
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
            
            lazy[node] = 0;
        }
    }
    
    // Add val to all elements in [l, r]
    void updateRange(int l, int r, long long val) {
        updateRange(1, 0, n - 1, l, r, val);
    }
    
    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) {
            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];
    }
    
    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
    
    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];
        
        pushDown(node, start, end);
        
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, l, r) +
               query(2 * node + 1, mid + 1, end, l, r);
    }
};

​
Range Set (Assignment) with Lazy

class LazySetSegTree {
public:
    int n;
    vector<long long> tree, lazy;
    vector<bool> hasLazy;
    
    LazySetSegTree(int n) : n(n), tree(4 * n, 0), 
                             lazy(4 * n, 0), hasLazy(4 * n, false) {}
    
    void pushDown(int node, int start, int end) {
        if (hasLazy[node]) {
            int mid = (start + end) / 2;
            
            tree[2 * node] = lazy[node] * (mid - start + 1);
            tree[2 * node + 1] = lazy[node] * (end - mid);
            
            lazy[2 * node] = lazy[2 * node + 1] = lazy[node];
            hasLazy[2 * node] = hasLazy[2 * node + 1] = true;
            
            hasLazy[node] = false;
        }
    }
    
    // Set all elements in [l, r] to val
    void setRange(int l, int r, long long val) {
        setRange(1, 0, n - 1, l, r, val);
    }
    
    void setRange(int node, int start, int end, int l, int r, long long val) {
        if (r < start || end < l) return;
        
        if (l <= start && end <= r) {
            tree[node] = val * (end - start + 1);
            lazy[node] = val;
            hasLazy[node] = true;
            return;
        }
        
        pushDown(node, start, end);
        
        int mid = (start + end) / 2;
        setRange(2 * node, start, mid, l, r, val);
        setRange(2 * node + 1, mid + 1, end, l, r, val);
        
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
};

​
Pattern 1: Coordinate Compression + Segment Tree

Problem: Count distinct elements, or handle values up to 10^9. 
// Compress values to [0, n-1]
vector<int> arr;  // Original array
vector<int> sorted_arr = arr;
sort(sorted_arr.begin(), sorted_arr.end());
sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());

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

// Now use compress(arr[i]) as index in segment tree

​
Pattern 2: Count Inversions with Segment Tree

long long countInversions(vector<int>& arr) {
    int n = arr.size();
    
    // Coordinate compression
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());
    
    auto compress = [&](int x) {
        return lower_bound(sorted_arr.begin(), sorted_arr.end(), x) - sorted_arr.begin();
    };
    
    SegTree st(sorted_arr.size());
    long long inversions = 0;
    
    // Process from right to left
    for (int i = n - 1; i >= 0; i--) {
        int compressed = compress(arr[i]);
        inversions += st.query(0, compressed - 1);  // Count smaller elements to the right
        st.update(compressed, st.query(compressed, compressed) + 1);
    }
    
    return inversions;
}

​
Pattern 3: Range Queries Offline

Problem: Answer queries more efficiently by processing in smart order. 
// Process queries sorted by right endpoint
struct Query {
    int l, r, idx;
};

vector<Query> queries(q);
for (int i = 0; i < q; i++) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].idx = i;
}

sort(queries.begin(), queries.end(), [](auto& a, auto& b) {
    return a.r < b.r;
});

vector<long long> answers(q);
int j = 0;

for (auto& [l, r, idx] : queries) {
    while (j <= r) {
        // Add element j to segment tree
        j++;
    }
    answers[idx] = st.query(l, r);
}

​
Pattern 4: Segment Tree on Indices

Problem: Track positions where something is true. 
// Find leftmost index in [l, r] where arr[i] > x
int findFirst(int node, int start, int end, int l, int r, int x) {
    if (r < start || end < l || tree[node] <= x) return -1;
    
    if (start == end) return start;
    
    int mid = (start + end) / 2;
    int left = findFirst(2 * node, start, mid, l, r, x);
    if (left != -1) return left;
    return findFirst(2 * node + 1, mid + 1, end, l, r, x);
}

​
Pattern 5: 2D Segment Tree

For 2D range queries (less common, but powerful). 
class SegTree2D {
public:
    int n, m;
    vector<vector<long long>> tree;
    
    SegTree2D(int n, int m) : n(n), m(m), tree(4 * n, vector<long long>(4 * m, 0)) {}
    
    void updateY(int nodeX, int startX, int endX, int nodeY, int startY, int endY, 
                 int x, int y, long long val) {
        if (startY == endY) {
            if (startX == endX) {
                tree[nodeX][nodeY] = val;
            } else {
                tree[nodeX][nodeY] = tree[2 * nodeX][nodeY] + tree[2 * nodeX + 1][nodeY];
            }
            return;
        }
        
        int midY = (startY + endY) / 2;
        if (y <= midY) {
            updateY(nodeX, startX, endX, 2 * nodeY, startY, midY, x, y, val);
        } else {
            updateY(nodeX, startX, endX, 2 * nodeY + 1, midY + 1, endY, x, y, val);
        }
        tree[nodeX][nodeY] = tree[nodeX][2 * nodeY] + tree[nodeX][2 * nodeY + 1];
    }
    
    void update(int x, int y, long long val) {
        updateX(1, 0, n - 1, x, y, val);
    }
    
    void updateX(int nodeX, int startX, int endX, int x, int y, long long val) {
        if (startX != endX) {
            int midX = (startX + endX) / 2;
            if (x <= midX) {
                updateX(2 * nodeX, startX, midX, x, y, val);
            } else {
                updateX(2 * nodeX + 1, midX + 1, endX, x, y, val);
            }
        }
        updateY(nodeX, startX, endX, 1, 0, m - 1, x, y, val);
    }
};

​
Common Mistakes

Mistake 1: Wrong array size Segment tree needs 4n space, not 2n.
vector<long long> tree(4 * n);  // CORRECT
Mistake 2: Forgetting to push lazy Always call pushDown before recursing in lazy segment tree.
Mistake 3: Wrong identity element
  • Sum: 0
  • Min: LLONG_MAX
  • Max: LLONG_MIN
  • GCD: 0
Mistake 4: 0-indexing vs 1-indexing Be consistent. The template above uses 0-indexed arrays.

​
Practice Problems

​
Beginner (1000-1300)

ProblemPatternLink
Range Sum QueriesPoint updateCSES
Range Minimum QueriesStaticCSES
Dynamic Range SumPoint updateCSES

​
Intermediate (1300-1600)

ProblemPatternLink
Range Update QueriesLazy propagationCSES
Range Xor QueriesPrefix XORCSES
Salary QueriesCoordinate compressionCSES

​
Advanced (1600-1900)

ProblemPatternLink
Polynomial QueriesLazy with coefficientsCSES
Range Updates and SumsDual lazyCSES

​
Key Takeaways

O(log n) Queries

Both point updates and range queries in logarithmic time.

Lazy Propagation

Defer updates until needed for O(log n) range updates.

4n Space

Always allocate 4n space for the tree array.

Combine Function

Customize for sum, min, max, GCD, or any associative operation.

​
Next Up

Chapter 18: String Algorithms

Master hashing, KMP, Z-function, and Trie for string problems.