Segment Tree Problem

Jul 8, 2025
Updated 7 hours ago
9 min read
Abhijeet Singh Rajput
Abhijeet Singh Rajput
@abhijeetsingh

Segment Tree Problems in C++: Range Queries, Updates & Lazy Propagation

Topic: Solving real segment tree problems in C++ — range sum queries, range min queries, frequency counting, and lazy propagation range updates — with full working code and traced examples.

If you've studied the segment tree data structure, the next step is putting it into practice. Segment trees shine when you need to answer range queries and handle updates on an array — both in O(log n) time. This post walks through four progressively harder problems, each with a complete C++ implementation and a traced example.

Quick Recap: How a Segment Tree Works

A segment tree is a binary tree where:

  • Each leaf stores one element of the array

  • Each internal node stores a combined result (sum, min, max, etc.) of its children's range

  • The root covers the full array

  • Tree size is 4 * n to safely accommodate all nodes

Every query and update traverses the tree using three cases: no overlap (return early), complete overlap (return stored value), and partial overlap (recurse on both children).

For a visual walkthrough of the structure, CP-Algorithms has one of the best segment tree references available.

Problem 1: Range Sum Query + Point Update

LeetCode 307 — Range Sum Query (Mutable)

The classic segment tree problem. Given an array, support two operations: query the sum of a range [ql, qr], and update a single index to a new value.

Code

cpp
class SegmentTree {
    vector<int> tree;
    int n;

    void build(const vector<int>& nums, int root, int left, int right) {
        if (left == right) {
            tree[root] = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        build(nums, 2 * root + 1, left, mid);
        build(nums, 2 * root + 2, mid + 1, right);
        tree[root] = tree[2 * root + 1] + tree[2 * root + 2];
    }

    int rangeQuery(int root, int left, int right, int ql, int qr) {
        if (qr < left || ql > right) return 0;          // no overlap
        if (ql <= left && qr >= right) return tree[root]; // complete overlap
        int mid = left + (right - left) / 2;
        int leftSum  = rangeQuery(2 * root + 1, left, mid, ql, qr);
        int rightSum = rangeQuery(2 * root + 2, mid + 1, right, ql, qr);
        return leftSum + rightSum;
    }

    void pointUpdate(int root, int left, int right, int idx, int val) {
        if (left == right) {
            tree[root] = val;
            return;
        }
        int mid = left + (right - left) / 2;
        if (idx <= mid) pointUpdate(2 * root + 1, left, mid, idx, val);
        else            pointUpdate(2 * root + 2, mid + 1, right, idx, val);
        tree[root] = tree[2 * root + 1] + tree[2 * root + 2];
    }

public:
    SegmentTree(const vector<int>& nums) {
        n = nums.size();
        tree.resize(4 * n, 0);
        build(nums, 0, 0, n - 1);
    }

    int query(int ql, int qr) {
        return rangeQuery(0, 0, n - 1, ql, qr);
    }

    void update(int idx, int val) {
        pointUpdate(0, 0, n - 1, idx, val);
    }
};

Example Trace

plaintext
Input array: [1, 3, 5, 7, 9, 11]

q 0 2  → sum of [1,3,5]    = 9
q 1 3  → sum of [3,5,7]    = 15
u 1 10 → array becomes [1,10,5,7,9,11]
q 0 2  → sum of [1,10,5]   = 16
q 1 3  → sum of [10,5,7]   = 22
q 0 0  → sum of [1]        = 1
q 5 5  → sum of [11]       = 11

Problem 2: Range Min Query + Point Update

Same structure as Problem 1, but instead of summing, each node stores the minimum of its range. The no-overlap base case returns INT_MAX so it doesn't accidentally contaminate the minimum.

Code

cpp
class SegmentTree {
    vector<int> tree;
    int n;

    void build(const vector<int>& nums, int root, int left, int right) {
        if (left == right) {
            tree[root] = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        build(nums, 2 * root + 1, left, mid);
        build(nums, 2 * root + 2, mid + 1, right);
        tree[root] = min(tree[2 * root + 1], tree[2 * root + 2]);
    }

    int query(int root, int left, int right, int ql, int qr) {
        if (qr < left || ql > right) return INT_MAX;       // no overlap
        if (ql <= left && qr >= right) return tree[root];  // complete overlap
        int mid = left + (right - left) / 2;
        int leftMin  = query(root * 2 + 1, left, mid, ql, qr);
        int rightMin = query(root * 2 + 2, mid + 1, right, ql, qr);
        return min(leftMin, rightMin);
    }

    void pointUpdate(int root, int left, int right, int index, int value) {
        if (left == right) {
            tree[root] = value;
            return;
        }
        int mid = left + (right - left) / 2;
        if (index <= mid) pointUpdate(root * 2 + 1, left, mid, index, value);
        else              pointUpdate(root * 2 + 2, mid + 1, right, index, value);
        tree[root] = min(tree[root * 2 + 1], tree[root * 2 + 2]);
    }

public:
    SegmentTree(const vector<int>& nums) {
        this->n = nums.size();
        tree.resize(n * 4);
        build(nums, 0, 0, n - 1);
    }

    int rangeMin(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    void update(int index, int value) {
        pointUpdate(0, 0, n - 1, index, value);
    }
};

Example Trace

plaintext
Input array: [4, 2, 5, 1, 9, 3]

query 0 3  → min of [4,2,5,1]  = 1
update 2 0 → array becomes [4,2,0,1,9,3]
query 0 3  → min of [4,2,0,1]  = 0
update 4 6 → array becomes [4,2,0,1,6,3]
query 3 5  → min of [1,6,3]    = 1

Problem 3: Count Frequency of K in Online Queries

Each node stores a hash map of {value → frequency} for all elements in its range. At query time, simply look up k in the root-level map of the queried range.

This is a more memory-intensive approach — useful when element values aren't bounded and you need flexible frequency lookups.

Code

cpp
class SegmentTree {
    vector<unordered_map<int, int>> tree;
    int n;

    void mergeLeftRight(int root) {
        tree[root].clear();
        for (const auto& [num, freq] : tree[2 * root + 1])
            tree[root][num] += freq;
        for (const auto& [num, freq] : tree[2 * root + 2])
            tree[root][num] += freq;
    }

    void build(const vector<int>& nums, int root, int left, int right) {
        if (left == right) {
            tree[root][nums[left]] = 1;
            return;
        }
        int mid = left + (right - left) / 2;
        build(nums, 2 * root + 1, left, mid);
        build(nums, 2 * root + 2, mid + 1, right);
        mergeLeftRight(root);
    }

    void pointUpdate(int root, int left, int right, int index, int val) {
        if (left == right) {
            tree[root].clear();
            tree[root][val] = 1;
            return;
        }
        int mid = left + (right - left) / 2;
        if (index <= mid) pointUpdate(2 * root + 1, left, mid, index, val);
        else              pointUpdate(2 * root + 2, mid + 1, right, index, val);
        mergeLeftRight(root);
    }

    int query(int root, int left, int right, int ql, int qr, int k) {
        if (qr < left || ql > right) return 0;
        if (ql <= left && qr >= right) return tree[root].count(k) ? tree[root].at(k) : 0;
        int mid = left + (right - left) / 2;
        return query(2 * root + 1, left, mid, ql, qr, k)
             + query(2 * root + 2, mid + 1, right, ql, qr, k);
    }

public:
    SegmentTree(const vector<int>& nums) {
        this->n = nums.size();
        tree.resize(4 * n);
        build(nums, 0, 0, n - 1);
    }

    void update(int index, int val) {
        pointUpdate(0, 0, n - 1, index, val);
    }

    int countFreq(int left, int right, int k) {
        return query(0, 0, n - 1, left, right, k);
    }
};

Example Trace

plaintext
Input array: [1, 3, 1, 2, 1, 3, 2]

countFreq 0 6 of 1  → 3   (three 1s in full array)
countFreq 2 4 of 3  → 0   (no 3 in [1,2,1])
countFreq 1 5 of 2  → 1   (one 2 in [3,1,2,1,3])
update idx 3 → value 3
countFreq 0 6 of 3  → 3   (now three 3s)

Problem 4: Range Update + Range Query (Lazy Propagation)

The hardest and most important variant. Without lazy propagation, a range update on [ql, qr] would require O(n) individual point updates. Lazy propagation defers updates — tagging a node with a pending value and only pushing it down when the node is actually visited.

Key Idea

  • lazyTree[node] stores a pending addition that hasn't been applied to children yet

  • Before any query or update at a node, call propagate() to flush the pending value downward

  • This keeps both updates and queries at O(log n)

Code

cpp
class SegmentTree {
    vector<int> tree;
    vector<int> lazyTree;
    int n;

    void build(const vector<int>& nums, int root, int left, int right) {
        if (left == right) {
            tree[root] = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        build(nums, root * 2 + 1, left, mid);
        build(nums, root * 2 + 2, mid + 1, right);
        tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
    }

    void propagate(int root, int left, int right) {
        if (lazyTree[root] == 0) return;
        tree[root] += (right - left + 1) * lazyTree[root];
        if (left != right) {  // push down to children (non-leaf)
            lazyTree[root * 2 + 1] += lazyTree[root];
            lazyTree[root * 2 + 2] += lazyTree[root];
        }
        lazyTree[root] = 0;
    }

    void update(int root, int left, int right, int ql, int qr, int val) {
        propagate(root, left, right);
        if (ql > right || qr < left) return;
        if (ql <= left && qr >= right) {
            lazyTree[root] = val;
            propagate(root, left, right);
            return;
        }
        int mid = left + (right - left) / 2;
        update(root * 2 + 1, left, mid, ql, qr, val);
        update(root * 2 + 2, mid + 1, right, ql, qr, val);
        tree[root] = tree[root * 2 + 1] + tree[root * 2 + 2];
    }

    int query(int root, int left, int right, int ql, int qr) {
        propagate(root, left, right);
        if (ql > right || qr < left) return 0;
        if (ql <= left && qr >= right) return tree[root];
        int mid = left + (right - left) / 2;
        int leftSum  = query(root * 2 + 1, left, mid, ql, qr);
        int rightSum = query(root * 2 + 2, mid + 1, right, ql, qr);
        return leftSum + rightSum;
    }

public:
    SegmentTree(const vector<int>& nums) {
        this->n = nums.size();
        tree.resize(n * 4, 0);
        lazyTree.resize(n * 4, 0);
        build(nums, 0, 0, n - 1);
    }

    int rangeSum(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    void rangeUpdate(int left, int right, int value) {
        update(0, 0, n - 1, left, right, value);
    }
};

Example Trace

plaintext
Input array: [0, 0, 0, 0, 0]

rangeUpdate 1 3 by +5 → array becomes [0, 5, 5, 5, 0]
rangeSum    0 4       → 15
rangeUpdate 0 2 by +2 → array becomes [2, 7, 7, 5, 0]
rangeSum    0 2       → 16
rangeSum    3 4       → 5
rangeSum    1 1       → 7

Complexity Summary

Operation

Time Complexity

Space

Build

O(n)

O(4n)

Point Update

O(log n)

—

Range Query

O(log n)

—

Range Update (Lazy)

O(log n)

O(4n) for lazy array

Frequency Query

O(log n)

O(n log n) for hash maps

Common Mistakes to Avoid

  • Tree size too small — always allocate 4 * n nodes, not 2 * n. For n = 6, the tree can need up to 24 nodes.

  • Forgetting to propagate before querying — in the lazy propagation version, skipping propagate() gives stale results.

  • Using INT_MAX for sum base case — range sum returns 0 for no-overlap; range min returns INT_MAX. Mixing these up causes overflow.

  • Not resetting lazyTree[root] = 0 after propagating — the pending value must be cleared or it gets applied twice.

For more practice problems, LeetCode's segment tree tag has a well-curated list sorted by difficulty.

Also Explore These Topics

Written by Abhijeet Singh Rajput · Published on Notehub