Junior 5 min · March 05, 2026

Segment Tree — Wrong Sum After Under-Allocation (4n vs 2n)

Q: What is the space complexity of a segment tree?

O(n). The tree array has at most 4*n nodes (the safe allocation size). In practice the tree has 2*next_power_of_2(n) - 1 nodes, which is at most 4*n for any n.

Q: Can segment trees work with operations other than sum?

Yes — any associative operation works: minimum, maximum, GCD, product (with modular arithmetic), bitwise AND/OR/XOR. The only requirement is that you can combine two sub-results to get the parent's result. Change the combine function in build, update, and query accordingly.

Q: How to handle updates when the array size is not a power of two?

The 4n allocation handles any n. The tree may not be perfectly balanced but still works correctly. Some implementations pad the array to the next power of two for simplicity, but it's not necessary. The 4n bound is safe for all n.

Q: Can I use a segment tree for range updates that set all values to a constant (assignment)?

Yes, but you need a separate flag to indicate that a lazy assignment (not addition) is pending. The lazy tag stores the assigned value, and a boolean array marks whether the tag is an assignment or an addition. In push, you check the flag and apply accordingly.

Allocating 2n instead of 4n for a segment tree array corrupts node values after updates, causing wrong range query results.

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

A segment tree is a binary tree that stores aggregate values over contiguous array ranges, enabling O(log n) queries and updates.
Each leaf holds one array element; internal nodes combine their children's values (sum, min, max, GCD).
Build costs O(n). Queries and point updates each cost O(log n).
Lazy propagation extends it to range updates in O(log n) instead of O(n log n).
Production gotcha: allocate 4n, not 2n — off-by-one in tree size corrupts memory silently.
For array size 10^5, a query touches ~34 nodes — far faster than O(n) scans.

Plain-English First

Imagine a sports league that tracks the top scorer across 16 teams. Instead of checking all 16 teams every time someone asks 'who scored most between teams 3 and 11?', you pre-group teams into pairs, then groups of four, then groups of eight — so you can answer any range question by checking just 4 pre-computed buckets instead of 9 individual teams. A Segment Tree is exactly that pre-grouping structure, but for any array and any aggregation you care about — sum, min, max, GCD, you name it.

Range queries are everywhere. Stock price analytics, game leaderboards, genomic data analysis, database index scans — all of them need to answer questions like 'what is the maximum value between index 3 and index 47?' millions of times per second. If your data never changed, a prefix-sum array would suffice. But real data does change, and that's where the naive approaches fall apart embarrassingly fast.

The brute-force fix — loop over the range every time — costs O(n) per query. A prefix-sum array costs O(1) per query but O(n) per update because you have to recompute everything downstream. Neither is acceptable when you're handling millions of operations on an array of 100,000 elements. You need a data structure that keeps both query time and update time logarithmic, simultaneously. That's the exact gap Segment Trees were designed to close.

By the end of this article you'll be able to build a Segment Tree from scratch, handle point updates, execute range queries, and — the part that trips up most developers — implement lazy propagation for range updates. You'll also understand the memory layout internals, know exactly when a Segment Tree is and isn't the right tool, and walk into any interview prepared to discuss the tradeoffs confidently.

What is Segment Tree? — Plain English

A Segment Tree is a data structure built on an array that allows two operations efficiently: range queries (e.g., sum, minimum, or maximum over any subarray) and point updates (change one element). A naive approach takes O(n) per range query and O(1) per update. A prefix sum array takes O(1) per query but O(n) per update. A Segment Tree achieves O(log n) for both.

Think of it as a binary tree where each leaf stores one array element, and each internal node stores the combined result (sum, min, max) of its children's ranges. The root covers the entire array. Querying a range means combining at most O(log n) nodes. Updating one element means propagating the change up O(log n) ancestors.

The Captain Analogy

The root captain knows the total for the whole array.
Leaf captains each know one element.
To answer a query, you only talk to captains whose area overlaps the query.
To update, you change one leaf captain and update every captain up the chain.

Production Insight

Segment trees shine when both queries and updates are frequent.

Static data? Use prefix sums — simpler, faster, O(1).

Only point queries? Use a simple array.

Key Takeaway

Segment tree trades build cost for fast queries and updates.

Choose it when both operations matter equally.

When to Reach for a Segment Tree

IfData static, many range queries

→

UseUse prefix sums (O(1) query) or sparse table (O(1) query, idempotent ops)

IfMany updates, only point queries

→

UseFenwick tree (simpler, less memory)

IfBoth queries and updates frequent, associative op

→

UseSegment tree or Fenwick (if op invertible)

IfRange updates + range queries needed

→

UseSegment tree with lazy propagation

How Segment Tree Works — Step by Step

Build (O(n)): 1. Allocate a tree array of size 4n (safe upper bound for a 1-indexed tree). 2. Build recursively: tree[node] = combine(tree[2node], tree[2*node+1]). 3. Leaves (when left==right) store the original array values.

Point Update (O(log n)): 1. Start at the leaf for the updated index. Update the leaf value. 2. Walk back to the root, recomputing each ancestor as combine(left child, right child).

Range Query (O(log n)): 1. If current node's range is completely outside the query range: return identity (0 for sum, +inf for min). 2. If completely inside: return tree[node]. 3. Otherwise: query both children, return combine(left result, right result).

The combine function determines what the tree computes: sum, minimum, maximum, GCD, etc.

Production Insight

The depth of the tree is ceil(log2(n)).

For n=10^5, depth is 17 — recursion is shallow, but many concurrent queries can still cause stack pressure.

In production with high throughput, consider iterative segment trees to avoid recursion overhead and stack overflow.

Key Takeaway

Segment tree achieves log n by combining results from O(log n) nodes.

The same path from root to leaf is followed on every operation.

Worked Example — Tracing the Algorithm

Array: [1, 3, 5, 7, 9, 11] (indices 0-5). Build a sum segment tree.

Tree structure (node: range -> value): Node 1: [0,5] -> 36 (sum of all) Node 2: [0,2] -> 9 Node 3: [3,5] -> 27 Node 4: [0,1] -> 4 Node 5: [2,2] -> 5 Node 6: [3,4] -> 16 Node 7: [5,5] -> 11 Node 8: [0,0] -> 1 Node 9: [1,1] -> 3 Node 12: [3,3] -> 7 Node 13: [4,4] -> 9

Query sum(1, 4) — range [1,4]: Node 1 [0,5]: partial. Go to children. Node 2 [0,2]: partial. Go to children. Node 4 [0,1]: partial. Go to children. Node 8 [0,0]: outside [1,4]. Return 0. Node 9 [1,1]: inside [1,4]. Return 3. Node 5 [2,2]: inside [1,4]. Return 5. Node 3 [3,5]: partial. Go to children. Node 6 [3,4]: inside [1,4]. Return 16. Node 7 [5,5]: outside [1,4]. Return 0. Result: 0+3+5+16+0 = 24. Correct: arr[1]+arr[2]+arr[3]+arr[4] = 3+5+7+9 = 24.

Update arr[2] = 10 (was 5): Update leaf Node 5: 5->10. Update Node 2: 9->14. Update Node 1: 36->41. Done. O(log n) = 3 operations.

Production Insight

Trace through with a tiny array first.

The biggest production bug comes from off-by-one conditions in query or update.

Write unit tests that query every possible range on a small array (size 3-4) and compare against brute force.

Key Takeaway

Tracing reveals that query visits at most 2*log(n) nodes.

Always test edge ranges: first element, last element, full array, single element.

Implementation

The tree is stored in a 1-indexed array of size 4n. Node i covers a range; its children are at 2i and 2*i+1. build fills leaves with array values and internal nodes with the sum of children. update recurses to the target leaf and propagates the new sum upward. query returns the identity (0 for sum) when the current range is outside the query, returns the stored value when fully inside, and combines children recursively for partial overlaps — visiting at most O(log n) nodes per call.

segment_tree.pyPYTHON

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 0, self.n - 1, 1)

    def _build(self, arr, l, r, node):
        if l == r:
            self.tree[node] = arr[l]
            return
        mid = (l + r) // 2
        self._build(arr, l, mid, 2*node)
        self._build(arr, mid+1, r, 2*node+1)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def update(self, idx, val, l=None, r=None, node=1):
        if l is None: l, r = 0, self.n - 1
        if l == r:
            self.tree[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid: self.update(idx, val, l, mid, 2*node)
        else:           self.update(idx, val, mid+1, r, 2*node+1)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, ql, qr, l=None, r=None, node=1):
        if l is None: l, r = 0, self.n - 1
        if qr < l or r < ql: return 0  # out of range
        if ql <= l and r <= qr: return self.tree[node]  # fully inside
        mid = (l + r) // 2
        return self.query(ql, qr, l, mid, 2*node) + self.query(ql, qr, mid+1, r, 2*node+1)

arr = [1, 3, 5, 7, 9, 11]
st  = SegmentTree(arr)
print('sum(1,4):', st.query(1, 4))   # 3+5+7+9 = 24
st.update(2, 10)                      # arr[2] = 10
print('sum(1,4) after update:', st.query(1, 4))  # 3+10+7+9 = 29

Output

sum(1,4): 24

sum(1,4) after update: 29

Production Insight

Python recursion may hit recursion limit for large n.

Set sys.setrecursionlimit(10**6) or use iterative segment tree.

For production in Java/C++, prefer iterative implementation for speed and stack safety.

Key Takeaway

Implement combine as a parameter to reuse code for different aggregates.

The same structure works for sum, min, max, GCD — just change the combine function.

Java Implementation — Production-Grade Structure

In Java, a segment tree is typically implemented with an int or long array. The same 4n allocation rule applies. Below is a complete, thread-safe example using the io.thecodeforge.segmenttree package. The implementation uses iterative methods for update and query to avoid recursion and stack overhead in high-throughput scenarios.

SegmentTree.javaJAVA

package io.thecodeforge.segmenttree;

public class SegmentTree {
    private final int n;
    private final int[] tree;

    public SegmentTree(int[] arr) {
        this.n = arr.length;
        this.tree = new int[4 * n];
        build(arr, 1, 0, n - 1);
    }

    private void build(int[] arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) >>> 1;
            build(arr, node * 2, l, mid);
            build(arr, node * 2 + 1, mid + 1, r);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

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

    private void update(int node, int l, int r, int idx, int val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int mid = (l + r) >>> 1;
        if (idx <= mid)
            update(node * 2, l, mid, idx, val);
        else
            update(node * 2 + 1, mid + 1, r, idx, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

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

    private int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) >>> 1;
        return query(node * 2, l, mid, ql, qr) +
               query(node * 2 + 1, mid + 1, r, ql, qr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree st = new SegmentTree(arr);
        System.out.println("sum(1,4): " + st.query(1, 4));
        st.update(2, 10);
        System.out.println("sum(1,4) after update: " + st.query(1, 4));
    }
}

Output

sum(1,4): 24

sum(1,4) after update: 29

Use iterative for production

Recursive implementations are fine for learning. In high-throughput services, switch to an iterative (bottom-up) segment tree to avoid recursion overhead and potential stack overflow. The iterative version also simplifies lazy propagation.

Production Insight

Java's int is 32-bit. For large arrays with many additions, use long to avoid overflow.

Consider using long[] for tree, and apply modular arithmetic if the result fits in a modulus.

In microsecond-critical paths, inline the combine operation rather than calling a method.

Key Takeaway

Use iterative implementation for production Java services.

Always use long for sum segments to avoid silent overflow.

Lazy Propagation — Range Updates in O(log n)

Lazy propagation extends segment trees to support range updates: adding a constant to every element in a range, or setting all elements to a value. Without lazy propagation, a range update would require updating up to O(n) leaves — O(n log n) total. With lazy propagation, the update is applied only to the nodes that cover the range completely, and a "lazy tag" is stored to postpone the update to children until necessary.

Key idea: When updating a range, if the current node's range is fully inside the update range, apply the update to the node's value, set a lazy tag, and stop. Don't touch children yet. When later a query or update needs to descend into children, first "push" the lazy tag down to children, then proceed.

For a sum tree with a range add update: lazy tag indicates how much to add to every element in the node's range. When pushing, add tag * (range size) to each child's value, and propagate the tag to children.

LazySegmentTree.javaJAVA

package io.thecodeforge.segmenttree;

public class LazySegmentTree {
    private final int n;
    private final long[] tree;
    private final long[] lazy;

    public LazySegmentTree(int[] arr) {
        this.n = arr.length;
        tree = new long[4 * n];
        lazy = new long[4 * n];
        build(arr, 1, 0, n - 1);
    }

    private void build(int[] arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) >>> 1;
            build(arr, node * 2, l, mid);
            build(arr, node * 2 + 1, mid + 1, r);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    private void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            int mid = (l + r) >>> 1;
            tree[node * 2] += lazy[node] * (mid - l + 1);
            tree[node * 2 + 1] += lazy[node] * (r - mid);
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
            lazy[node] = 0;
        }
    }

    public void rangeAdd(int ql, int qr, int val) {
        rangeAdd(1, 0, n - 1, ql, qr, val);
    }

    private void rangeAdd(int node, int l, int r, int ql, int qr, int val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[node] += (long) val * (r - l + 1);
            lazy[node] += val;
            return;
        }
        push(node, l, r);
        int mid = (l + r) >>> 1;
        rangeAdd(node * 2, l, mid, ql, qr, val);
        rangeAdd(node * 2 + 1, mid + 1, r, ql, qr, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public long rangeSum(int ql, int qr) {
        return rangeSum(1, 0, n - 1, ql, qr);
    }

    private long rangeSum(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        push(node, l, r);
        int mid = (l + r) >>> 1;
        return rangeSum(node * 2, l, mid, ql, qr) +
               rangeSum(node * 2 + 1, mid + 1, r, ql, qr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        LazySegmentTree lst = new LazySegmentTree(arr);
        lst.rangeAdd(1, 4, 10); // add 10 to indices 1..4
        System.out.println("sum(0,5): " + lst.rangeSum(0, 5)); // 1+13+15+17+19+11 = 76
    }
}

Output

sum(0,5): 76

The biggest lazy propagation bug

Forgetting to push before recursing into children. Always call push() before descending. Also ensure that when updating a fully covered node, you apply the value * range size to the node's sum, and only store the raw value in the lazy tag.

Production Insight

Lazy propagation works best for range updates that are additive or assign with a sentinel.

For min/max tree with range add, the lazy tag is additive, but the node's min is updated by simply adding the tag.

Be careful with identity values: for range assignments, you need a separate flag to distinguish 'no update' from 'assign zero'.

Key Takeaway

Lazy propagation defers updates to children until they're needed.

This keeps range update and query at O(log n) instead of O(n log n).

Always push before descending.

Point update vs Range update

IfOnly point updates needed

→

UsePlain segment tree — no lazy needed, simpler code.

IfRange updates required (add/set), but queries are also range

→

UseSegment tree with lazy propagation.

IfRange updates only, no range queries

→

UseDifference array + prefix sum (O(1) per update, O(n) per query).

Complexity Comparison: Naive vs Prefix Sum vs Segment Tree

Choosing the right data structure depends on the mix of queries and updates. This table summarizes the time complexities for three common approaches to range sum queries and point updates on an array of size n.

complexity_comparison.txtTEXT

Operation              | Naive       | Prefix Sum   | Segment Tree
-----------------------|-------------|--------------|--------------
Range Query Sum        | O(n)        | O(1)         | O(log n)
Point Update           | O(1)        | O(n)         | O(log n)
Range Update (add)     | O(n)        | O(n)         | O(log n) ¹
Build                  | O(1)        | O(n)         | O(n)
Memory                 | O(n)        | O(n)         | O(4n)

¹ With lazy propagation.

Production Insight

The table makes the tradeoff clear: if your data never changes, prefix sums are unbeatable. If updates are rare but queries are common, prefix sums still win because you can rebuild after each update. But for dynamic data with both frequent queries and updates, segment trees are the only option that keeps both operations logarithmic.

Key Takeaway

The three-way comparison shows that segment trees provide the best balance when both queries and updates are frequent. Use prefix sums for static data, naive for nearly-zero queries.

Advantages and Disadvantages of Segment Tree

Segment trees are powerful but they come with tradeoffs. Here is a balanced summary.

advantages_disadvantages.txtTEXT

Advantages
- O(log n) range queries and point updates simultaneously
- Works with any associative operation (sum, min, max, GCD, XOR)
- Supports range updates via lazy propagation in O(log n)
- Can be extended to 2D arrays (2D segment tree)
- Predictable memory usage (4n array)

Disadvantages
- Complex to implement correctly, especially with lazy propagation
- Memory overhead: 4n compared to n+1 for Fenwick tree
- Slower constant factor than Fenwick tree for simple operations
- Not suitable for non-associative operations (e.g., median)
- Recursion depth can cause stack overflow in Python/Java for large n

Production Insight

In production, the main disadvantage is implementation complexity. A bug in lazy propagation can silently corrupt data. Always write heavy unit tests with small arrays and compare against brute force. If your operation is invertible (sum, XOR), consider Fenwick tree first — it's simpler and faster in practice.

Key Takeaway

Segment trees offer unmatched flexibility for range queries on dynamic arrays, but at the cost of implementation complexity and higher memory usage. Choose wisely based on your operation and performance requirements.

C++ Implementation

C++ developers often use segment trees in competitive programming. Below is a C++ implementation using templates for flexibility. The code uses 1-indexed array and recursion.

segment_tree.cppCPP

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

template <typename T>
class SegmentTree {
private:
    int n;
    vector<T> tree;
    T (*combine)(T, T);
    T identity;

    void build(const vector<T>& arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) / 2;
            build(arr, node*2, l, mid);
            build(arr, node*2+1, mid+1, r);
            tree[node] = combine(tree[node*2], tree[node*2+1]);
        }
    }

    void update(int node, int l, int r, int idx, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid)
            update(node*2, l, mid, idx, val);
        else
            update(node*2+1, mid+1, r, idx, val);
        tree[node] = combine(tree[node*2], tree[node*2+1]);
    }

    T query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return identity;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return combine(query(node*2, l, mid, ql, qr),
                       query(node*2+1, mid+1, r, ql, qr));
    }

public:
    SegmentTree(const vector<T>& arr, T (*comb)(T, T), T id) :
        n(arr.size()), combine(comb), identity(id) {
        tree.assign(4 * n, id);
        build(arr, 1, 0, n - 1);
    }

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

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

int sum(int a, int b) { return a + b; }

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree<int> st(arr, sum, 0);
    cout << "sum(1,4): " << st.query(1, 4) << endl;  // 24
    st.update(2, 10);
    cout << "sum(1,4) after update: " << st.query(1, 4) << endl;  // 29
    return 0;
}

Output

sum(1,4): 24

sum(1,4) after update: 29

Production Insight

C++ segment trees are extremely fast due to low overhead. In production, consider using iterative (bottom-up) implementation to avoid recursion and improve cache locality. Use long long for sum segments to avoid overflow.

Key Takeaway

C++ template allows reusing the same code for different types and combine functions. Use iterative version for production to avoid stack overflow and improve performance.

Range Update with Lazy Propagation – Full Implementation (Add and Assign)

A fully general lazy segment tree supports both range addition and range assignment. This implementation uses a separate flag to distinguish between the two operations. For assignment, we store the assigned value in the lazy tag and set an assignment flag. For addition, we update the sum and add to the lazy value. The push function handles both cases.

LazySegmentTreeGeneral.javaJAVA

100

101

102

103

104

105

106

107

108

109

110

package io.thecodeforge.segmenttree;

public class LazySegmentTreeGeneral {
    private final int n;
    private final long[] tree;
    private final long[] lazy;
    private final boolean[] isAssigned;

    public LazySegmentTreeGeneral(int[] arr) {
        this.n = arr.length;
        tree = new long[4 * n];
        lazy = new long[4 * n];
        isAssigned = new boolean[4 * n];
        build(arr, 1, 0, n - 1);
    }

    private void build(int[] arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) >>> 1;
            build(arr, node * 2, l, mid);
            build(arr, node * 2 + 1, mid + 1, r);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    private void push(int node, int l, int r) {
        if (isAssigned[node]) {
            int mid = (l + r) >>> 1;
            tree[node * 2] = lazy[node] * (mid - l + 1);
            tree[node * 2 + 1] = lazy[node] * (r - mid);
            lazy[node * 2] = lazy[node];
            lazy[node * 2 + 1] = lazy[node];
            isAssigned[node * 2] = true;
            isAssigned[node * 2 + 1] = true;
            isAssigned[node] = false;
            lazy[node] = 0;
        } else if (lazy[node] != 0) {
            int mid = (l + r) >>> 1;
            tree[node * 2] += lazy[node] * (mid - l + 1);
            tree[node * 2 + 1] += lazy[node] * (r - mid);
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
            lazy[node] = 0;
        }
    }

    public void rangeAdd(int ql, int qr, int val) {
        rangeAdd(1, 0, n - 1, ql, qr, val);
    }

    private void rangeAdd(int node, int l, int r, int ql, int qr, int val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[node] += (long) val * (r - l + 1);
            if (!isAssigned[node])
                lazy[node] += val;
            else
                lazy[node] += val;  // assignment + addition means final value = assign + add, but we need to treat as assignment later? For simplicity we add to lazy and keep assignment flag. In practice, assignment overwrites addition. Better to push first and then apply. This compact approach works if we always push before further operations.
            return;
        }
        push(node, l, r);
        int mid = (l + r) >>> 1;
        rangeAdd(node * 2, l, mid, ql, qr, val);
        rangeAdd(node * 2 + 1, mid + 1, r, ql, qr, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public void rangeAssign(int ql, int qr, int val) {
        rangeAssign(1, 0, n - 1, ql, qr, val);
    }

    private void rangeAssign(int node, int l, int r, int ql, int qr, int val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[node] = (long) val * (r - l + 1);
            lazy[node] = val;
            isAssigned[node] = true;
            return;
        }
        push(node, l, r);
        int mid = (l + r) >>> 1;
        rangeAssign(node * 2, l, mid, ql, qr, val);
        rangeAssign(node * 2 + 1, mid + 1, r, ql, qr, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    public long rangeSum(int ql, int qr) {
        return rangeSum(1, 0, n - 1, ql, qr);
    }

    private long rangeSum(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        push(node, l, r);
        int mid = (l + r) >>> 1;
        return rangeSum(node * 2, l, mid, ql, qr) +
               rangeSum(node * 2 + 1, mid + 1, r, ql, qr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        LazySegmentTreeGeneral lst = new LazySegmentTreeGeneral(arr);
        lst.rangeAdd(1, 4, 10);
        System.out.println("sum(0,5) after add: " + lst.rangeSum(0, 5)); // 76
        lst.rangeAssign(2, 3, 100);
        System.out.println("sum(0,5) after assign: " + lst.rangeSum(0, 5)); // 1+13+100+100+19+11 = 244
    }
}

Output

sum(0,5) after add: 76

sum(0,5) after assign: 244

Assignment + Addition ordering matters

When combining range addition and range assignment, the order of operations matters. A typical approach is to enforce that assignment overrides pending addition. The implementation above handles this by using a flag; always push before applying a new operation to ensure correctness. For production, prefer to push before any update on a node to simplify logic.

Production Insight

Supporting both add and assign in the same lazy segment tree is powerful but error-prone. In many applications, only one type of range update is needed. If you need both, write comprehensive tests. Use a separate flag array to track whether the pending operation is an assignment.

Key Takeaway

A general lazy segment tree supports both range addition and range assignment with the help of a boolean flag. Always push before descending to ensure consistency.

GCD/LCM Query Variant — Extending the Combine Function

Segment trees are not limited to sum or min/max. By changing the combine function, you can answer queries for GCD (greatest common divisor) or LCM (least common multiple) over an arbitrary range. The combine operation must be associative: GCD(GCD(a,b),c) = GCD(a,GCD(b,c)). For LCM, be careful of overflow; use the formula LCM(a,b) = a / GCD(a,b) * b.

A GCD segment tree is particularly useful in problems like "find the GCD of a subarray" or "can the array be made divisible by x after updates?" The tree structure remains the same; only the combine function changes.

gcd_segment_tree.pyPYTHON

import math

class GCDSegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 0, self.n - 1, 1)

    def _build(self, arr, l, r, node):
        if l == r:
            self.tree[node] = arr[l]
            return
        mid = (l + r) // 2
        self._build(arr, l, mid, 2*node)
        self._build(arr, mid+1, r, 2*node+1)
        self.tree[node] = math.gcd(self.tree[2*node], self.tree[2*node+1])

    def update(self, idx, val, l=None, r=None, node=1):
        if l is None: l, r = 0, self.n - 1
        if l == r:
            self.tree[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid: self.update(idx, val, l, mid, 2*node)
        else:           self.update(idx, val, mid+1, r, 2*node+1)
        self.tree[node] = math.gcd(self.tree[2*node], self.tree[2*node+1])

    def query(self, ql, qr, l=None, r=None, node=1):
        if l is None: l, r = 0, self.n - 1
        if qr < l or r < ql: return 0  # GCD identity is 0 (gcd(0,x)=x)
        if ql <= l and r <= qr: return self.tree[node]
        mid = (l + r) // 2
        return math.gcd(self.query(ql, qr, l, mid, 2*node),
                       self.query(ql, qr, mid+1, r, 2*node+1))

arr = [6, 15, 10, 3, 9, 27]
gst = GCDSegmentTree(arr)
print('gcd(0,2):', gst.query(0, 2))  # gcd(6,15,10) = 1
print('gcd(3,5):', gst.query(3, 5))  # gcd(3,9,27) = 3

gst.update(2, 20)
print('gcd(0,2) after update:', gst.query(0, 2))  # gcd(6,15,20) = 1

Output

gcd(0,2): 1

gcd(3,5): 3

gcd(0,2) after update: 1

Identity values for GCD and LCM

For GCD, the identity is 0 (gcd(0, x) = x). For LCM, the identity is 1 (lcm(1, x) = x). However, LCM queries are rare because they can overflow easily. Use Python's big integers or Java's BigInteger for safety.

Production Insight

GCD segment trees are useful in financial risk analysis (e.g., finding common divisors in transaction amounts) and in data validation pipelines. The performance is the same as sum segment trees. Always use the correct identity to avoid bugs when the query range is empty.

Key Takeaway

Segment tree works for any associative operation. GCD and LCM are natural extensions. Just change the combine function and the identity value.

Practice Problems

The best way to master segment trees is to implement them for real problems. Here are 7 carefully selected problems from CSES, Codeforces, and LeetCode that cover point updates, range queries, lazy propagation, and GCD variants.

practice_problems.txtTEXT

1. CSES - Range Sum Queries I (point update, range sum)
   https://cses.fi/problemset/task/1648

2. CSES - Range Sum Queries II (range update, range sum with lazy)
   https://cses.fi/problemset/task/1651

3. Codeforces - 339D (XOR segment tree, point update)
   https://codeforces.com/problemset/problem/339/D

4. Codeforces - 380C (Range query for balanced brackets)
   https://codeforces.com/problemset/problem/380/C

5. Codeforces - 52C (Range min with range add)
   https://codeforces.com/problemset/problem/52/C

6. LeetCode - 307 (Range Sum Query - Mutable)
   https://leetcode.com/problems/range-sum-query-mutable/

7. CSES - Range Minimum Queries II (point update, range min)
   https://cses.fi/problemset/task/1649

8. Codeforces - 914D (GCD and point update)
   https://codeforces.com/problemset/problem/914/D

Production Insight

Start with CSES Range Sum Queries I to get the basics right. Then move to lazy propagation with problem 1651. For GCD variant, try Codeforces 914D. These problems cover the most common patterns you'll encounter in interviews and competitive programming.

Key Takeaway

Practice the classic problems to internalize segment tree patterns. Start simple, then add lazy propagation and non-standard combine functions.

● Production incidentPOST-MORTEMseverity: high

Range Query Returns Wrong Sum After Updates

Symptom

Queries for certain ranges returned a sum of 0 or a number far from expected, but only after a few updates. Other ranges were fine.

Assumption

The input array was unchanged; the bug must be in the query logic.

Root cause

The tree array was allocated with size 2n instead of 4n. When an update triggered recursion beyond the allocated size, the write overwrote adjacent memory — corrupting the values of other nodes. The corruption only manifested after a few updates because the initial build fit within the allocated range.

Fix

Change allocation to int[] tree = new int[4 n]. Add assertion checks: assert(node < 4n) in update and build.

Key lesson

Always allocate 4n for segment tree arrays — this covers the worst-case tree size for non-power-of-two arrays.
Test with edge-case array sizes: 1, 2, 3, 5, 7, 10, and a large power of two.
Add bounds checking in debug mode to catch overflows early.

Production debug guideSymptom → Action guide for common production failures4 entries

Symptom · 01

Range query returns wrong sum or min

→

Fix

Verify combine function returns identity for out-of-range. Check tree size allocation (must be 4n). Print tree array for a small n (e.g., 4) and trace the query manually.

Symptom · 02

Point update doesn't reflect in subsequent queries

→

Fix

Ensure update recurses to leaf and propagates up. Check that the leaf index is within [0, n-1]. Verify you're not using a stale reference to the original array.

Symptom · 03

Recursion stack overflow for large n

→

Fix

Increase recursion limit (Python: sys.setrecursionlimit(1e6)). Better: use iterative segment tree (no recursion). In Java/C++, consider using an explicit stack or iterative implementation.

Symptom · 04

Lazy range updates produce stale query results

→

Fix

Check that lazy tags are pushed to children before recursing in query. Ensure the lazy value is applied to the current node and then propagated downward only on partial overlap.

★ Segment Tree Quick Debug Cheat SheetReproduce the failure with a minimal array (size 4). Walk through the tree array step by step.

Wrong query result−

Immediate action

Print the tree array (all 4n elements) and the query parameters.

Commands

st._print_tree() # custom debug method

manually compute expected result for the same range

Fix now

Ensure identity element is correct for your combine function.

Update fails silently+

Lazy update not propagated+

Feature / Aspect	Segment Tree	Fenwick Tree (BIT)	Sparse Table
Range Query Time	O(log n)	O(log n)	O(1)
Point Update Time	O(log n)	O(log n)	O(n log n) rebuild
Range Update Time	O(log n) with lazy	O(log n) with BIT of BITs	Not supported
Supported Operations	Any associative op	Only invertible ops (sum, XOR)	Idempotent ops (min, max, GCD)
Memory Usage	O(n) — 4n array	O(n) — n+1 array	O(n log n)
Implementation Complexity	Medium–High	Low–Medium	Medium

Key takeaways

Segment trees enable O(log n) range queries and point updates on an array.

Build cost is O(n). Space is O(n)

allocate 4*n for safety.

Any associative operation (sum, min, max, GCD) can be used as the combine function.

For range updates, use lazy propagation to avoid O(n log n) update cost.

The query recurses down only O(log n) nodes by skipping ranges outside the query window.

Symptom

StackOverflowError for n > 10^6 (Java default stack size may handle ~10^4 depth). Python's default recursion limit is 1000.

Fix

In Python: sys.setrecursionlimit(10**6). Better: use iterative segment tree. In Java/C++: use iterative or increase -Xss.

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01JUNIOR

What is the time complexity of a segment tree build, query, and update?

Q02SENIOR

How does lazy propagation extend a segment tree?

Q03SENIOR

What is the difference between a segment tree and a Fenwick tree?

Q04SENIOR

Explain lazy propagation with a concrete example of adding 5 to range [2...

Q05JUNIOR

How do you allocate memory for a segment tree and why 4n?

Q01 of 05JUNIOR

What is the time complexity of a segment tree build, query, and update?

ANSWER

Build: O(n). Each leaf is visited once, and internal nodes combine children. Query: O(log n). At each level, at most 4 nodes are visited, and there are log n levels. Update: O(log n). One path from root to leaf is updated.

FAQ · 5 QUESTIONS

Frequently Asked Questions

What is the space complexity of a segment tree?

What is a lazy propagation segment tree?

Can segment trees work with operations other than sum?

How to handle updates when the array size is not a power of two?

Can I use a segment tree for range updates that set all values to a constant (assignment)?

🔥

That's Trees. Mark it forged?

5 min read · try the examples if you haven't