Segment Trees

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:

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)
Push Down: Before accessing children, push the lazy value down to them
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)

Problem	Pattern	Link
Range Sum Queries	Point update	CSES
Range Minimum Queries	Static	CSES
Dynamic Range Sum	Point update	CSES

Intermediate (1300-1600)

Problem	Pattern	Link
Range Update Queries	Lazy propagation	CSES
Range Xor Queries	Prefix XOR	CSES
Salary Queries	Coordinate compression	CSES

Advanced (1600-1900)

Problem	Pattern	Link
Polynomial Queries	Lazy with coefficients	CSES
Range Updates and Sums	Dual lazy	CSES

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.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Segment Trees

Segment Trees

Why Segment Trees?

Basic Segment Tree (Point Update, Range Query)

Usage

Segment Tree for Different Operations

Lazy Propagation (Range Updates)

Range Set (Assignment) with Lazy

Pattern 1: Coordinate Compression + Segment Tree

Pattern 2: Count Inversions with Segment Tree

Pattern 3: Range Queries Offline

Pattern 4: Segment Tree on Indices

Pattern 5: 2D Segment Tree

Common Mistakes

Practice Problems

Beginner (1000-1300)

Intermediate (1300-1600)

Advanced (1600-1900)

Key Takeaways

O(log n) Queries

Lazy Propagation

4n Space

Combine Function

Next Up

Chapter 18: String Algorithms

​Segment Trees

​Why Segment Trees?

​Basic Segment Tree (Point Update, Range Query)

​Usage

​Segment Tree for Different Operations

​Lazy Propagation (Range Updates)

​Range Set (Assignment) with Lazy

​Pattern 1: Coordinate Compression + Segment Tree

​Pattern 2: Count Inversions with Segment Tree

​Pattern 3: Range Queries Offline

​Pattern 4: Segment Tree on Indices

​Pattern 5: 2D Segment Tree

​Common Mistakes

​Practice Problems

​Beginner (1000-1300)

​Intermediate (1300-1600)

​Advanced (1600-1900)

​Key Takeaways

O(log n) Queries

Lazy Propagation

4n Space

Combine Function

​Next Up

Chapter 18: String Algorithms

Segment Trees

Why Segment Trees?

Basic Segment Tree (Point Update, Range Query)

Usage

Segment Tree for Different Operations

Lazy Propagation (Range Updates)

Range Set (Assignment) with Lazy

Pattern 1: Coordinate Compression + Segment Tree

Pattern 2: Count Inversions with Segment Tree

Pattern 3: Range Queries Offline

Pattern 4: Segment Tree on Indices

Pattern 5: 2D Segment Tree

Common Mistakes

Practice Problems

Beginner (1000-1300)

Intermediate (1300-1600)

Advanced (1600-1900)

Key Takeaways

Next Up