1. What is a Segment Tree?

A Segment Tree is a binary tree data structure used to efficiently answer range queries and perform updates on an array.

Without a segment tree:

• Range Sum → O(n)
• Point Update → O(1)

With a segment tree:

• Range Sum → O(log n)
• Point Update → O(log n)

It is useful when an array changes frequently and we need many range queries.

Visualization

2. When should I use it?

Use a segment tree when you have both:

• Updates on the array
• Range queries

Examples:

• Sum of a range
• Maximum in a range
• Minimum in a range
• GCD of a range
• XOR of a range
• Product of a range
• Custom information (maximum subarray sum, frequency, etc.)

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

template<typename T>
class SegmentTree {
private:
    int n;              // Size of the original array
    vector<T> tree;     // Segment tree (4*n is enough)

    //---------------------------------------------------
    // Merge function
    // Defines what each node stores.
    // Change this depending on the problem.
    //---------------------------------------------------
    T merge(T left, T right) {
        return left + right;          // Range Sum
        // return max(left, right);   // Range Maximum
        // return min(left, right);   // Range Minimum
        // return __gcd(left, right); // Range GCD
    }

    //---------------------------------------------------
    // Identity element
    // Returned when a segment contributes nothing.
    //---------------------------------------------------
    T identity() {
        return 0;          // Sum
        // return INT_MIN; // Maximum
        // return INT_MAX; // Minimum
    }

    //---------------------------------------------------
    // Build the tree
    //
    // node  -> current node in the segment tree
    // start -> left boundary of represented segment
    // end   -> right boundary of represented segment
    //---------------------------------------------------
    void build(int node, int start, int end, const vector<T>& arr) {

        // Leaf node
        if (start == end) {
            tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;

        // Build left half
        build(2 * node, start, mid, arr);

        // Build right half
        build(2 * node + 1, mid + 1, end, arr);

        // Combine children
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    //---------------------------------------------------
    // Point Update
    //
    // Update arr[idx] = value
    //---------------------------------------------------
    void update(int node, int start, int end, int idx, T value) {

        // Reached the element to update
        if (start == end) {
            tree[node] = value;
            return;
        }

        int mid = (start + end) / 2;

        // Decide which child contains idx
        if (idx <= mid)
            update(2 * node, start, mid, idx, value);
        else
            update(2 * node + 1, mid + 1, end, idx, value);

        // Recompute current node
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    //---------------------------------------------------
    // Range Query
    //
    // Returns answer for interval [l, r]
    //---------------------------------------------------
    T query(int node, int start, int end, int l, int r) {

        // Case 1: No overlap
        //
        //                 l------r
        //  start------end
        //
        if (r < start || end < l)
            return identity();

        // Case 2: Complete overlap
        //
        // l------------------r
        //    start------end
        //
        if (l <= start && end <= r)
            return tree[node];

        // Case 3: Partial overlap
        //
        //        l---------r
        // start--------end
        //
        int mid = (start + end) / 2;

        T leftAnswer = query(2 * node, start, mid, l, r);
        T rightAnswer = query(2 * node + 1, mid + 1, end, l, r);

        return merge(leftAnswer, rightAnswer);
    }

public:

    //---------------------------------------------------
    // Constructor
    //---------------------------------------------------
    SegmentTree(const vector<T>& arr) {
        n = arr.size();
        tree.assign(4 * n, identity());

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

    //---------------------------------------------------
    // Public point update
    //---------------------------------------------------
    void update(int idx, T value) {
        update(1, 0, n - 1, idx, value);
    }

    //---------------------------------------------------
    // Public range query
    //---------------------------------------------------
    T query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

int main() {

    vector<int> a = {1, 2, 3, 4, 5};

    SegmentTree<int> st(a);

    // Sum of indices [1..3]
    cout << st.query(1, 3) << '\n';   // 9

    // a[2] = 10
    st.update(2, 10);

    cout << st.query(1, 3) << '\n';   // 16
}

3. Applications

Segment trees are commonly used for:

• Range Sum Query
• Range Maximum Query
• Range Minimum Query
• Range GCD Query
• Range XOR Query
• Frequency counting
• Maximum subarray sum
• Order statistics (with augmented nodes)
• Lazy propagation (range updates)
• Many advanced competitive programming problems