Skip to main content

​
Overview

Segment trees are one of the most powerful and flexible data structures in competitive programming. They support range queries and updates in O(log n) time for any associative operation.
Time Complexity
  • Build: O(n)
  • Query: O(log n)
  • Update: O(log n) for both point and range updates (with lazy propagation)
Space Complexity: O(4n)

​
Basic Segment Tree

The basic segment tree supports point updates and range queries efficiently using a bottom-up approach.

​
Implementation

range_query_segment_tree.cpp
template <typename T, class F = function<T(const T &, const T &)>>
class SegmentTree {
    T NEUTRAL;
    int n;
    vector<T> tree;
    F func;

  public:
    SegmentTree(const vector<T> &values, T neutral, const F &f) : func(f) {
        NEUTRAL = neutral;
        n = values.size();
        tree.resize(n * 2);
        // Build
        for (int i = 0; i < n; i++) {
            tree[n + i] = values[i];
        }
        for (int i = n - 1; i > 0; --i) {
            tree[i] = func(tree[i * 2], tree[i * 2 + 1]);
        }
    }

    void modify(int index, T value) {
        tree[index + n] = value;
        index = index + n;
        for (int i = index; i > 1; i >>= 1) {
            tree[i / 2] = func(tree[i], tree[i ^ 1]);
        }
    }

    T query(int l, int r) {
        T ans = NEUTRAL;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                ans = func(ans, tree[l++]);
            }
            if (r & 1) {
                ans = func(ans, tree[--r]);
            }
        }
        return ans;
    }
};
template <typename T> using segtree = SegmentTree<T>;

​
Usage Examples

vector<int> values = {3, 1, 4, 1, 5, 9, 2, 6};

// Create segment tree for maximum queries
auto func = [](int x, int y) { return max(x, y); };
segtree<int, decltype(func)> st(values, -1e9, func);

// Query maximum in range [2, 5]
int max_val = st.query(2, 6);  // Returns 9 (half-open interval)

// Update index 4 to 10
st.modify(4, 10);

// Query again
max_val = st.query(2, 6);  // Returns 10

​
Segment Tree with Lazy Propagation

Lazy propagation enables efficient range updates by deferring updates until necessary.

​
Full Implementation

range_query_segment_tree_lazy_full.cpp
template <typename T> class SegmentTree {
  public:
    static const T lazy_neutral = static_cast<T>(0);

    struct Node {
        T lazy = lazy_neutral;
        T mx = static_cast<T>(-1e9);
        T mn = static_cast<T>(1e9);
        T sum = static_cast<T>(0);
        int idx_mn = -1;
        int idx_mx = -1;
        bool changed = false;

        void apply(int left, int right, T value) {
            lazy = value;
            mx = value;
            mn = value;
            sum = (right - left + 1) * value;
            if (left == right) {
                idx_mn = left;
                idx_mx = left;
            }
            changed = true;
        }
    };

    Node unite(const Node &a, const Node &b) const {
        Node res;
        res.sum = a.sum + b.sum;
        res.mx = max(a.mx, b.mx);
        res.mn = min(a.mn, b.mn);
        res.idx_mn = (res.mn == a.mn ? a.idx_mn : b.idx_mn);
        res.idx_mx = (res.mx == a.mx ? a.idx_mx : b.idx_mx);
        return res;
    }

    inline void push(int x, int left, int right) {
        int y = (left + right) >> 1;
        int z = x + ((y - left + 1) << 1);
        if (tree[x].lazy != lazy_neutral || tree[x].changed) {
            tree[x + 1].apply(left, y, tree[x].lazy);
            tree[z].apply(y + 1, right, tree[x].lazy);
            tree[x].lazy = lazy_neutral;
        }
    }

    inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); }

    int n;
    vector<Node> tree;

    SegmentTree(int _n) : n(_n) {
        assert(n > 0);
        tree.resize(2 * n - 1);
        build(0, 0, n - 1);
    }

    SegmentTree(const vector<T> &v) {
        n = v.size();
        assert(n > 0);
        tree.resize(2 * n - 1);
        build(0, 0, n - 1, v);
    }

    Node query(int left, int right) {
        assert(0 <= left && left <= right && right <= n - 1);
        return query(0, 0, n - 1, left, right);
    }

    template <typename... M> void modify(int left, int right, const M &...v) {
        assert(0 <= left && left <= right && right <= n - 1);
        modify(0, 0, n - 1, left, right, v...);
    }

    // Private methods omitted for brevity
};
template <typename T> using segtree = SegmentTree<T>;

​
Usage Examples

int n = 10;
segtree<int> st(n);

// Set all elements in [2, 7] to 5
st.modify(2, 7, 5);

// Query range [3, 6]
auto result = st.query(3, 6);
cout << "Sum: " << result.sum << endl;      // Sum: 20 (4 * 5)
cout << "Max: " << result.mx << endl;       // Max: 5
cout << "Min: " << result.mn << endl;       // Min: 5
cout << "Max index: " << result.idx_mx << endl;  // 3

​
Binary Search on Segment Tree

Segment trees support efficient binary search operations to find the first/last position satisfying a condition. 
// Find first index in [l, r] where sum >= k
segtree<int> st(values);
int pos = st.find_first(l, r, [&](const auto& node) {
    return node.sum >= k;
});

// Find last index in [l, r] where max < threshold
int pos = st.find_last(l, r, [&](const auto& node) {
    return node.mx < threshold;
});

​
Common Applications

Range Sum Queries

Track cumulative values with point or range updates

Range Min/Max Queries

Find extrema in ranges with dynamic updates

Coordinate Compression

Map large coordinate spaces to smaller ranges

2D Range Queries

Nested segment trees for 2D operations

​
Practice Problems

  1. Range Sum Query - Mutable (LeetCode 307)
  2. Range Minimum Query (CSES)
  3. Dynamic Range Sum Queries (CSES)
  4. Hotel Queries (CSES) - Binary search on segment tree

​
See Also

Build docs developers (and LLMs) love

Get started for freeTalk to us