Segment Tree Explained: Range Queries, Updates and Lazy Propagation

Here's a bug that catches almost everyone the first time. You write a recursive segment tree, allocate an array of size 2n because "a binary tree with n leaves has 2n - 1 nodes" and test it on 8 elements. It works. You test it on 5 elements. It works. Then someone feeds it 6 elements and it throws:

java.lang.ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 12

That's not a random failure. It happens for n = 6, 10, 11, 12, 13, 14, 18, ... and never for n = 5, 7, 8, 9. By the end of this article you'll know exactly why, along with everything else you need to use segment trees confidently: how they work, why they're fast, lazy propagation, the variants worth knowing, how they compare with Fenwick trees and sparse tables, the bugs that show up in real code and how to explain all of it in an interview.

The Problem: Range Queries on Changing Data

Picture an array of 100,000 numbers. Maybe they're hourly order counts for an online store, prices on a trading screen or seat states in a cinema hall. Your program has to answer two kinds of requests, over and over, mixed together in any order:

1. "What is the sum (or minimum or maximum) of the values between index L and index R?"
2. "The value at index i just changed. Store the new value."

The obvious approach loops from L to R for every question. That's O(n) per query. With 100,000 queries you're looking at up to 10 billion steps, which is far too slow for an interview problem with a time limit and wasteful for any service that has to respond quickly.

A segment tree fixes this. It answers range queries and handles updates in O(log n) time each. For 100,000 elements, log₂ n is about 17, so each operation touches a few dozen nodes instead of up to 100,000 elements.

Every Java snippet in this article was compiled and checked against a brute-force implementation over thousands of randomized test cases. The bug outputs and timings shown later are from real runs, not made-up examples.

Quick answer: segment tree in one minute

• What: a binary tree over an array where each node stores the answer (sum, min, max, ...) for one range.
• Why: answers range queries and handles updates in O(log n). Prefix sums can't update cheaply; plain arrays can't query cheaply.
• Build: O(n). Query / point update / range update (with lazy propagation): O(log n). Memory: 2n (iterative) to 4n (recursive) slots.
• Works for: any associative operation with an identity value, such as sum, min, max, GCD or custom structs.
• Use something simpler when: data never changes (prefix sums, sparse table) or you only need sums (Fenwick tree).

What Is a Segment Tree?

A segment tree is a binary tree built over an array where every node stores a precomputed answer (such as the sum, minimum or maximum) for one contiguous range of that array. The root covers the whole array, each child covers half of its parent's range and the leaves cover single elements. This lets you answer range queries and apply updates in O(log n) time.

A few terms first, since the rest of the article uses them:

• Range query: a question about a contiguous part of an array, for example "sum of elements from index 2 to 6".
• Point update: changing one element of the array.
• Range update: changing every element in a range, for example "add 10 to every element from index 1 to 4".
• Aggregate: the combined value of a range, such as its sum or minimum.
• Merge (or combine) function: the function that builds a parent's aggregate from its two children. For sums it is a + b. For minimums it is min(a, b).

Why Do We Need a Segment Tree?

Before reaching for a tree, it helps to see why the simpler options fall short.

Option 1: Plain array

Store the array as-is. Updating one element takes O(1). But a range sum needs a loop over the range, which is O(n) in the worst case.

Option 2: Prefix sum array

Precompute prefix[i] = arr[0] + ... + arr[i-1]. Now any range sum is prefix[R+1] - prefix[L], which is O(1). This is excellent when the data never changes.

The catch: if arr[3] changes, every prefix value after index 3 is now wrong. Fixing them costs O(n). Prefix sums also only work for operations you can "subtract out". There's no way to compute the minimum of [L, R] from two prefix minimums.

Option 3: Segment tree

Both operations become O(log n) and it works for sum, min, max, GCD and many other operations.

The segment tree doesn't win every column. It wins on balance. When reads and writes are both frequent, O(log n) for both beats being fast at one and slow at the other.

How a Segment Tree Is Structured

Let's build a sum segment tree for this array:

index:  0  1  2  3  4  5  6  7
value:  5  8  6  3  2  7  2  6

The root covers the whole range [0, 7]. It splits into [0, 3] and [4, 7]. Each of those splits again, until every node covers exactly one index. Each node stores the sum of its range:

                        ┌──────────┐
                        │ [0,7]=39 │
                        └────┬─────┘
               ┌─────────────┴─────────────┐
          ┌────┴─────┐                ┌────┴─────┐
          │ [0,3]=22 │                │ [4,7]=17 │
          └────┬─────┘                └────┬─────┘
         ┌─────┴─────┐               ┌─────┴─────┐
     ┌───┴────┐  ┌───┴───┐       ┌───┴───┐  ┌───┴───┐
     │[0,1]=13│  │[2,3]=9│       │[4,5]=9│  │[6,7]=8│
     └──┬──┬──┘  └──┬──┬─┘       └──┬──┬─┘  └──┬──┬─┘
        5  8        6  3            2  7       2  6      ← leaves

Three properties matter here:

1. Every node's value is the merge of its two children. [0,3] = 13 + 9 = 22.
2. The tree is balanced. Because each split halves the range, the height is ⌈log₂ n⌉. For 8 elements that is 3 levels below the root.
3. Any range can be assembled from a small number of nodes. Range [2, 6] is just [2,3] + [4,5] + [6,6]. We never need to look at individual elements one by one.

Storing the tree in an array

You don't need node objects with left and right pointers. The standard trick is the same one used by binary heaps:

• The root lives at index 1.
• The children of node i live at 2i and 2i + 1.
• The parent of node i is i / 2.

For our example, the array looks like this:

tree index:  1   2   3   4   5   6   7   8  9  10 11 12 13 14 15
value:      39  22  17  13   9   9   8   5  8   6  3  2  7  2  6
             └root┘  └─ internal ─┘     └──────── leaves ────────┘

Using index 1 for the root (instead of 0) keeps the child formulas clean. With a 0-based root you would need 2i + 1 and 2i + 2, which works but is easier to get wrong.

Why allocate 4n slots?

You will see new long[4 * n] in almost every recursive implementation and it is worth knowing why.

If n is a power of two, the tree is perfect and needs exactly 2n - 1 nodes. When n isn't a power of two, the recursive splitting produces a tree whose height is h = ⌈log₂ n⌉ and with the 2i / 2i + 1 numbering the largest index used can be as high as 2^(h+1) - 1. Since 2^h < 2n, that maximum index is below 4n. So 4n is a safe upper bound that avoids index-out-of-bounds errors.

This is where the bug from the introduction comes from. A short program that builds the recursive tree for every n and records the largest index it touches makes the pattern visible. Here's what it printed for a few sizes:

Two things stand out. First, the sizes that break 2n follow no obvious pattern, which is why the bug feels random. Second, 4n is tight in the worst case. Across every n from 1 to 20,000, the largest ratio of slots needed to n was about 3.95 (at n = 16,512, just above a power of two). So you can't shave 4n down to 3n and stay safe.

If you want the exact minimum, allocate 2 × 2^⌈log₂ n⌉ slots, which is the next power of two doubled. For n = 100,000 that's 262,144 instead of 400,000. It wastes some memory either way, which we'll come back to with the iterative version.

Building a Segment Tree

Building is a post-order recursion: build the left half, build the right half, then combine.

private void build(long[] arr, int node, int start, int end) {
    if (start == end) {              // leaf: covers exactly one element
        tree[node] = arr[start];
        return;
    }
    int mid = start + (end - start) / 2;
    build(arr, 2 * node, start, mid);
    build(arr, 2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Time complexity: O(n). There are about 2n - 1 real nodes and each is computed once in constant time. People sometimes guess O(n log n) here, but each node is visited exactly once, so it is linear.

Recursion depth: about log₂ n + 1. Even for 10 million elements that is around 25 frames, so stack overflow isn't a real concern for the build.

How a Range Query Works

To answer "sum of [left, right]", we start at the root and compare the node's range [start, end] with the query range. There are only three possibilities:

                 ┌──────────────────────────────────┐
                 │ Visit node covering [start, end] │
                 └─────────────────┬────────────────┘
                                   │
             How does it overlap the query [left, right]?
                                   │
        ┌──────────────────────────┼───────────────────────────┐
        ▼                          ▼                           ▼
┌────────────────┐     ┌───────────────────────┐    ┌──────────────────────┐
│  NO OVERLAP    │     │    TOTAL OVERLAP      │    │   PARTIAL OVERLAP    │
│ right < start  │     │ left ≤ start and      │    │  anything else       │
│ or end < left  │     │ end ≤ right           │    │                      │
├────────────────┤     ├───────────────────────┤    ├──────────────────────┤
│ return identity│     │ return tree[node]     │    │ query both children, │
│ (0 for sum)    │     │ and stop              │    │ merge the results    │
└────────────────┘     └───────────────────────┘    └──────────────────────┘

• No overlap: this node contributes nothing. Return the identity element, a value that doesn't change the result when merged. For sum it is 0. For min it is +∞ (in Java, Long.MAX_VALUE). For max it is -∞.
• Total overlap: the node's whole range is inside the query, so its stored value is exactly what we need. Stop here without going deeper. This is where all the speed comes from.
• Partial overlap: some of the node is inside the query and some is outside. Split the question between the two children.

private long query(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return 0;                          // no overlap
    }
    if (left <= start && end <= right) {
        return tree[node];                 // total overlap
    }
    int mid = start + (end - start) / 2;   // partial overlap
    return query(2 * node, start, mid, left, right)
         + query(2 * node + 1, mid + 1, end, left, right);
}

Dry run: sum of [2, 6]

Expected answer: 6 + 3 + 2 + 7 + 2 = 20.

Total: 0 + 9 + 9 + 2 + 0 = 20. We read three stored values instead of adding five elements. On an array of a million elements, the difference between "a handful of nodes" and "the whole range" is what makes the structure worth using.

How a Point Update Works

To change arr[index], walk from the root down to the leaf for that index, write the new value there and then recompute every ancestor on the way back up. Only the nodes on that one root-to-leaf path can change, because they are the only nodes whose range contains index.

private void update(int node, int start, int end, int index, long value) {
    if (start == end) {
        tree[node] = value;
        return;
    }
    int mid = start + (end - start) / 2;
    if (index <= mid) {
        update(2 * node, start, mid, index, value);
    } else {
        update(2 * node + 1, mid + 1, end, index, value);
    }
    tree[node] = tree[2 * node] + tree[2 * node + 1];   // recompute on the way back up
}

Dry run: set arr[3] = 10

Path visited:  [0,7] → [0,3] → [2,3] → [3,3]

[3,3]:  3  → 10
[2,3]:  9  → 6 + 10  = 16
[0,3]:  22 → 13 + 16 = 29
[0,7]:  39 → 29 + 17 = 46

Four nodes changed, one per level. That's O(log n).

Now query(2, 6) returns 16 + 9 + 2 = 27, which matches 6 + 10 + 2 + 7 + 2.

Complete Java Implementation (Sum Segment Tree)

Here is the whole thing in one class, with input validation. The public methods hide the recursive parameters so callers only deal with array indexes.

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

    public SegmentTree(long[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("array must not be empty");
        }
        this.n = arr.length;
        this.tree = new long[4 * n];
        build(arr, 1, 0, n - 1);
    }

    private void build(long[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // Set arr[index] = value
    public void update(int index, long value) {
        if (index < 0 || index >= n) {
            throw new IndexOutOfBoundsException("index " + index);
        }
        update(1, 0, n - 1, index, value);
    }

    private void update(int node, int start, int end, int index, long value) {
        if (start == end) {
            tree[node] = value;
            return;
        }
        int mid = start + (end - start) / 2;
        if (index <= mid) {
            update(2 * node, start, mid, index, value);
        } else {
            update(2 * node + 1, mid + 1, end, index, value);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // Sum of arr[left..right], both inclusive
    public long query(int left, int right) {
        if (left < 0 || right >= n || left > right) {
            throw new IllegalArgumentException("bad range [" + left + ", " + right + "]");
        }
        return query(1, 0, n - 1, left, right);
    }

    private long query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0;                       // no overlap: identity for sum
        }
        if (left <= start && end <= right) {
            return tree[node];              // total overlap
        }
        int mid = start + (end - start) / 2;  // partial overlap: ask both children
        return query(2 * node, start, mid, left, right)
             + query(2 * node + 1, mid + 1, end, left, right);
    }

    public static void main(String[] args) {
        long[] arr = {5, 8, 6, 3, 2, 7, 2, 6};
        SegmentTree st = new SegmentTree(arr);
        System.out.println(st.query(2, 6));  // 20
        st.update(3, 10);
        System.out.println(st.query(2, 6));  // 27
        System.out.println(st.query(0, 7));  // 46
    }
}

A few deliberate choices in this code:

• long instead of int. 100,000 values of up to 10⁹ sum to 10¹⁴, which overflows a 32-bit int silently. In Java, integer overflow doesn't throw; it wraps around and gives you a wrong answer.
• start + (end - start) / 2 instead of (start + end) / 2. For array indexes this rarely matters, but in the sparse variant later in this article the range can reach 10⁹ or more and start + end can overflow.
• Inclusive ranges [left, right]. Pick inclusive or half-open and stick to it everywhere. Mixing them is one of the most common sources of off-by-one bugs.

To turn this into a minimum segment tree, change three things: the merge (Math.min), the identity returned on no overlap (Long.MAX_VALUE) and nothing else. The structure stays identical.

Why Every Operation Is O(log n)

The update case is easy to see: one root-to-leaf path, one node per level.

The query case needs a short argument and it is a popular interview follow-up.

At any level of the tree, the nodes the query visits form a contiguous run (they all overlap one contiguous query range). Among them, only the leftmost and rightmost can be partially overlapping. Every node in between is fully inside the query, so it returns immediately without recursing. That means at most two nodes per level recurse further and each of them visits two children, so at most four nodes are visited per level. With about log₂ n levels, the total work is O(4 log n) = O(log n).

How Fast Is It in Practice?

Big-O tells you how cost grows. It doesn't tell you what you'll actually wait for, so here's a rough measurement. The setup: 100,000 random long values, then 100,000 random operations (half point updates, half range-sum queries over random ranges). The naive version loops over the range for each query. All three versions produced identical checksums.

Treat these numbers as an illustration, not a benchmark. They come from a simple System.nanoTime() loop (not JMH) on OpenJDK 21 running on a single-core cloud VM and the naive timings swung by more than 2x between rounds because of noise on a shared machine. Your hardware will give different absolute numbers. The shape is what matters: in these runs the tree was roughly 70 to 170 times faster than the loop and the gap widens as n grows. The iterative version's advantage over the recursive one comes from no recursion, half the memory and tighter loops; expect it to vary by JVM and CPU.

If you want numbers for your own system, run the same experiment with JMH, the Java microbenchmark harness, which handles warm-up and dead-code elimination properly.

What Can a Segment Tree Store?

Sum is the teaching example, but the real strength of a segment tree is that the merge function is pluggable. The rule for what works is precise:

1. The merge must be associative. merge(merge(a, b), c) must equal merge(a, merge(b, c)). The tree splits ranges at arbitrary midpoints, so the grouping of the computation changes depending on the query. Associativity guarantees the answer doesn't.
2. You need an identity element or some other way to handle "no overlap". This is the value e where merge(e, x) = x.

An operation with both properties is called a monoid in mathematics. You don't need to know that word to use a segment tree, but it is the term you'll see in advanced material and libraries.

Notice that commutativity isn't required. merge(a, b) doesn't have to equal merge(b, a), as long as you always merge the left child before the right child. This is what lets segment trees handle surprisingly rich queries.

The last row is a classic. To find the best subarray sum inside [L, R] with updates, each node keeps four numbers. The merged best answer is the larger of the left best, the right best or the left's best suffix plus the right's best prefix. This merge is associative but not commutative and it shows why storing a small struct per node is often the trick to a hard problem.

What a plain segment tree can't do directly

Some queries don't split cleanly:

• Median or k-th smallest in a range. Knowing the median of two halves doesn't give you the median of the whole. You need variants like a merge sort tree or a persistent segment tree (covered below).
• Number of distinct values in a range. The counts of two halves overlap in unknown ways. This is usually solved offline with sorting plus a Fenwick or segment tree or with a persistent segment tree.
• Mode (most frequent value). No compact summary merges correctly.

If you can't describe a fixed-size summary of a range that two halves can combine into, a basic segment tree isn't the right tool.

Walking Down the Tree: Finding the k-th Element

There's a second way to use a segment tree that many tutorials skip. Instead of asking "what is the sum of this range?", you ask "where does the running total reach k?" and you answer it by walking down from the root.

Example scenario (illustrative): a cinema seat map where arr[i] = 1 means seat i is free and 0 means it is taken. "Find the 5th free seat" means "find the smallest index where the prefix sum reaches 5". The same pattern applies to "find the k-th smallest value" when arr[v] counts how many times value v has been inserted.

At each node, look at the left child's sum. If it is at least k, the answer is in the left half. Otherwise, subtract the left sum from k and go right.

// Smallest index i such that arr[0] + ... + arr[i] >= k.
// Requires all values to be non-negative. Returns -1 if the total is less than k.
public int findPrefixAtLeast(long k) {
    if (tree[1] < k) return -1;
    int node = 1, start = 0, end = n - 1;
    while (start != end) {
        int mid = start + (end - start) / 2;
        if (tree[2 * node] >= k) {
            node = 2 * node;
            end = mid;
        } else {
            k -= tree[2 * node];
            node = 2 * node + 1;
            start = mid + 1;
        }
    }
    return start;
}

This runs in O(log n). The naive alternative, binary searching over the index and calling query(0, mid) each time, works too but costs O(log² n). The non-negative requirement matters: with negative values, prefix sums aren't monotonic, so "go left if the left sum is big enough" stops being a valid rule.

Lazy Propagation: Fast Range Updates

The problem

Point updates are O(log n). But what if the request is "add 10 to every element in [1, 4]"? Doing it as four point updates costs O(k log n) for a range of length k. For a range covering the whole array, that is worse than just rebuilding.

Realistic scenario (illustrative): an e-commerce admin applies a flat price adjustment to a whole block of product slots or a game server gives a buff to every player in a zone and the system still needs fast range totals afterward.

The idea

Be lazy. When an update fully covers a node, update that node's own aggregate and leave a note saying "my children still owe this update". Don't touch the children yet. Later, if some operation needs to go inside that node, it first hands the note down one level. This "handing down" is called pushing the lazy tag.

So each node now has two fields:

• sum[node]: the correct sum of its range, already including any pending update.
• lazy[node]: an update that has been applied to this node but not yet to its children.

For a range-add on a sum tree, applying "add v to every element" to a node of length len changes its sum by v × len.

Dry run: add 10 to [1, 4] on [5, 8, 6, 3, 2, 7, 2, 6]

                        ┌──────────┐
                        │ [0,7]=79 │   partial: recurse, then recompute
                        └────┬─────┘
               ┌─────────────┴─────────────┐
          ┌────┴─────┐                ┌────┴─────┐
          │ [0,3]=52 │                │ [4,7]=27 │   both partial
          └────┬─────┘                └────┬─────┘
         ┌─────┴──────┐              ┌─────┴─────┐
     ┌───┴────┐  ┌────┴─────┐    ┌───┴────┐  ┌───┴───┐
     │[0,1]=23│  │[2,3]=29  │    │[4,5]=19│  │[6,7]=8│  untouched
     └──┬──┬──┘  │lazy = +10│    └──┬──┬──┘  └───────┘
        5  18    └──┬──┬────┘       12 7
                    6  3   ← still old values; they owe +10

Look at [2,3]. Its sum jumped from 9 to 9 + 10 × 2 = 29 and it carries lazy = +10. Its leaves still say 6 and 3. That's fine, because nobody has asked about them yet. The root already holds the correct total of 39 + 10 × 4 = 79.

If a later query asks for [3, 3], it has to enter [2,3] (partial overlap). Before doing so, it pushes: the leaves become 16 and 13 and [2,3]'s lazy tag resets to 0. Then the query reads 13, which is correct.

 Update or query reaches a node
              │
              ▼
 ┌─────────────────────────────┐   yes   ┌──────────────────────────────────┐
 │ Does the operation fully    ├────────►│ Update: apply to this node, add  │
 │ cover this node's range?    │         │ to its lazy tag, STOP.           │
 └──────────────┬──────────────┘         │ Query: return the stored value.  │
                │ no (partial)           └──────────────────────────────────┘
                ▼
 ┌─────────────────────────────┐
 │ push(): give the pending    │
 │ tag to both children, then  │
 │ clear this node's tag       │
 └──────────────┬──────────────┘
                ▼
 ┌─────────────────────────────┐
 │ Recurse into the children   │
 └──────────────┬──────────────┘
                ▼
 ┌─────────────────────────────┐
 │ Update only: pull, i.e.     │
 │ recompute node from children│
 └─────────────────────────────┘

Lazy segment tree in Java (range add, range sum)

public class LazySegmentTree {
    private final long[] sum;   // sum of the segment
    private final long[] lazy;  // pending "add this to every element" for the children
    private final int n;

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

    private void build(long[] arr, int node, int start, int end) {
        if (start == end) { sum[node] = arr[start]; return; }
        int mid = start + (end - start) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        sum[node] = sum[2 * node] + sum[2 * node + 1];
    }

    // Apply "add value to every element" to a whole node, without touching its children
    private void apply(int node, int start, int end, long value) {
        sum[node] += value * (end - start + 1);
        lazy[node] += value;
    }

    // Hand the pending update down one level before we look inside a node
    private void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = start + (end - start) / 2;
            apply(2 * node, start, mid, lazy[node]);
            apply(2 * node + 1, mid + 1, end, lazy[node]);
            lazy[node] = 0;
        }
    }

    public void rangeAdd(int left, int right, long value) {
        rangeAdd(1, 0, n - 1, left, right, value);
    }

    private void rangeAdd(int node, int start, int end, int left, int right, long value) {
        if (right < start || end < left) return;
        if (left <= start && end <= right) {
            apply(node, start, end, value);
            return;
        }
        push(node, start, end);
        int mid = start + (end - start) / 2;
        rangeAdd(2 * node, start, mid, left, right, value);
        rangeAdd(2 * node + 1, mid + 1, end, left, right, value);
        sum[node] = sum[2 * node] + sum[2 * node + 1];
    }

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

    private long query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return 0;
        if (left <= start && end <= right) return sum[node];
        push(node, start, end);
        int mid = start + (end - start) / 2;
        return query(2 * node, start, mid, left, right)
             + query(2 * node + 1, mid + 1, end, left, right);
    }

    public static void main(String[] args) {
        LazySegmentTree st = new LazySegmentTree(new long[]{5, 8, 6, 3, 2, 7, 2, 6});
        st.rangeAdd(1, 4, 10);
        System.out.println(st.query(0, 7)); // 79
        System.out.println(st.query(3, 5)); // 13 + 12 + 7 = 32
    }
}

(Leaves can also receive a lazy tag through apply. It's never pushed from a leaf, so it is harmless and keeping apply uniform makes the code simpler.)

The rules that make lazy propagation correct

Lazy propagation works for an update type only if two things are true:

1. You can apply the update to a node's aggregate without looking at the children. Range-add on sums works because the new sum is old + v × length. Range-add on minimums works because the new min is old + v. Range "set every value to its square root" on sums does not work, because you can't compute the new sum from the old sum alone.
2. Two pending updates can be combined into one tag. Two adds combine into one bigger add. Two assignments combine into the later one.

Mixing update types needs care with order. Suppose you support both "assign x" and "add v" on the same tree. A clean way is to store a tag as "assign (optional), then add". A new assignment overwrites the whole tag. A new add is added to the assign value if one is pending or to the add part otherwise. If you get the order backwards, the bugs only appear on specific sequences of operations, which makes them painful to track down.

Iterative (Bottom-Up) Segment Tree

The recursive version is the easiest to reason about, but there's a compact non-recursive version that uses exactly 2n slots. It became popular in competitive programming largely through Al.Cash's Codeforces post "Efficient and easy segment trees", which is still worth reading if you want the bit tricks explained in more depth.

Layout: leaves live at tree[n .. 2n-1] and internal node i is the merge of tree[2i] and tree[2i+1]. Building is a single backward loop.

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

    public IterativeSegmentTree(long[] arr) {
        n = arr.length;
        tree = new long[2 * n];
        for (int i = 0; i < n; i++) tree[n + i] = arr[i];        // leaves
        for (int i = n - 1; i >= 1; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    public void update(int index, long value) {
        int i = index + n;
        tree[i] = value;
        for (i /= 2; i >= 1; i /= 2) tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    // Sum of arr[left..right], both inclusive
    public long query(int left, int right) {
        long sum = 0;
        int l = left + n, r = right + n + 1;   // half-open [l, r)
        while (l < r) {
            if ((l & 1) == 1) sum += tree[l++];
            if ((r & 1) == 1) sum += tree[--r];
            l /= 2;
            r /= 2;
        }
        return sum;
    }
}

The query walks two pointers up the tree. When the left pointer sits on a right child (odd index), that node's range is fully inside the query and its parent would stick out to the left, so we take the node and move one step right. The right pointer does the mirror image. Both then climb a level.

Things to know about this version:

• It works for any n, not just powers of two. When n isn't a power of two, some internal nodes merge elements that aren't neighbors in the original array. The query loop never reads those nodes for a valid range, so the answers stay correct. But it means the "walk down from the root" trick and lazy propagation don't map cleanly onto this layout. If you need them, pad n up to the next power of two.
• Non-commutative merges need two accumulators. The code above adds into one sum, which is fine for addition. For an order-sensitive merge (like the maximum-subarray struct), keep a left result and a right result separately: resLeft = merge(resLeft, tree[l++]) and resRight = merge(tree[--r], resRight), then return merge(resLeft, resRight).
• It uses half the memory of the 4n recursive layout and has no recursion overhead, which usually makes it faster in practice. The recursive version is easier to extend.

Advanced Variants

Dynamic (sparse) segment tree

What if indexes range from 0 to 10⁹, but only a few hundred thousand are ever used? An array of 4 × 10⁹ slots is impossible.

A dynamic segment tree creates nodes only when an update first touches them. Each update creates at most one new node per level, so about log₂(range) + 1 nodes, which is around 31 for a range of 10⁹.

// Sparse segment tree over a huge index range [lo, hi]. Nodes are created only when touched.
public class DynamicSegmentTree {
    private static final class Node {
        long sum;
        Node left, right;
    }

    private final Node root = new Node();
    private final long lo, hi;

    public DynamicSegmentTree(long lo, long hi) {
        this.lo = lo;
        this.hi = hi;
    }

    // arr[index] += delta
    public void add(long index, long delta) {
        Node node = root;
        long start = lo, end = hi;
        node.sum += delta;
        while (start != end) {
            long mid = start + (end - start) / 2;
            if (index <= mid) {
                if (node.left == null) node.left = new Node();
                node = node.left;
                end = mid;
            } else {
                if (node.right == null) node.right = new Node();
                node = node.right;
                start = mid + 1;
            }
            node.sum += delta;
        }
    }

    public long query(long left, long right) {
        return query(root, lo, hi, left, right);
    }

    private long query(Node node, long start, long end, long left, long right) {
        if (node == null || right < start || end < left) return 0;
        if (left <= start && end <= right) return node.sum;
        long mid = start + (end - start) / 2;
        return query(node.left, start, mid, left, right)
             + query(node.right, mid + 1, end, left, right);
    }
}

Memory is O(q log R) for q updates over a range of size R. The trade-off is pointer chasing and object allocation, which is slower than a flat array.

Coordinate compression

If you know every index in advance (you can read all queries first), you can avoid the sparse tree entirely. Sort the distinct coordinates, map each to its rank 0, 1, 2, ... and build a normal segment tree over the ranks. This is called coordinate compression. It's usually faster and simpler than a dynamic tree, but it requires an offline setting, where all inputs are available before processing begins. If coordinates arrive one by one and you must answer immediately (an online setting), the dynamic tree is the natural choice.

Persistent segment tree

A persistent data structure keeps every old version available after updates. A point update only changes the nodes on one root-to-leaf path. Instead of modifying them, a persistent segment tree creates new copies of those O(log n) nodes and shares every other node with the previous version. Each version gets its own root.

version 0 root ──► A ──► B ──► leaf(old)
                   │      └─► C
                   └─► D            (shared)

version 1 root ──► A' ─► B' ─► leaf(new)
                   │      └─► C     (shared with v0)
                   └─► D            (shared with v0)

Memory is O(n + q log n) for q updates. A classic use is answering "k-th smallest value in arr[L..R]": build version i by inserting arr[0..i-1] into a count tree over compressed values, then walk down versions R+1 and L together, using the difference in counts. Each query is O(log n).

Persistence also has a practical side effect for concurrent systems, covered in the production section.

Merge sort tree

Each node stores the sorted list of its range instead of a single number. Building it looks exactly like merge sort and it uses O(n log n) memory because every element appears once per level. It answers queries like "how many values in [L, R] are less than x?" by binary searching inside the O(log n) nodes that cover the range, for O(log² n) per query. It handles static data well but doesn't support cheap updates.

2D segment tree

For a grid, build a segment tree over rows where each node holds a segment tree over columns. Queries and point updates take O(log n × log m). Memory for a dense n × m grid is O(n × m) with a significant constant factor. In practice, 2D Fenwick trees are often preferred for sums because they are much smaller and simpler, while 2D segment trees are kept for operations like min and max.

Segment trees on trees (Euler tour and heavy-light decomposition)

Segment trees work on arrays, but many problems live on trees, such as an org chart or a category hierarchy. Two techniques bridge the gap:

• Euler tour (DFS order): number nodes in the order a depth-first search enters them. Every subtree becomes a contiguous range, so "sum of all values in the subtree of v" turns into a normal range query.
• Heavy-light decomposition (HLD): splits a tree into chains so any path between two nodes crosses O(log n) chains. Each chain is a contiguous range in a segment tree, so path queries cost O(log² n).

Segment Tree Beats

Some updates, like "replace every value in [L, R] with min(value, x)", break the lazy propagation rules because the new sum depends on more than the old sum. A technique known in competitive programming as Segment Tree Beats, popularized by Codeforces user jiry_2 in a 2018 post based on a report written about two years earlier, handles this by storing extra information per node (such as the maximum, the second maximum and the count of the maximum) and using an amortized argument for its running time. It's an advanced tool and rarely needed outside contests, but it is good to know it exists.

A Note on Naming: Two Different "Segment Trees"

This catches people out when they read computational geometry books.

In computational geometry, the name segment tree traditionally refers to a structure credited to Jon Louis Bentley, from his 1977 notes on Klee's rectangle problems. It's covered in detail in de Berg, Cheong, van Kreveld and Overmars, Computational Geometry: Algorithms and Applications (chapter 10). It stores a set of intervals and answers stabbing queries: "which intervals contain point x?" Each interval is stored in the O(log n) canonical nodes that cover it, using O(n log n) space and a query reports all k matching intervals in O(log n + k) time.

The structure most programmers mean today and the one this article covers, is the range query tree over an array. The two share the same recursive "split the range in half" skeleton, which is why the name is shared. When you read a paper or a textbook, check which one it means.

An interval tree is a third structure. It also answers "which stored intervals overlap this point or interval?", but it organizes intervals around center points and uses O(n) space.

Segment Tree vs Fenwick Tree vs Sparse Table vs Other Options

There's no single winner. The right choice depends on the operation, whether data changes and how much code complexity you can accept.

A quick decision guide

This is roughly the order I'd go through before writing any tree at all:

Does the data change after you build it?
│
├── No ──► Is the operation sum (or anything you can subtract)?
│          ├── Yes ──► Prefix sums. O(1) query, done.
│          └── No  ──► Is it min / max / gcd (overlap-safe)?
│                      ├── Yes ──► Sparse table. O(1) query.
│                      └── No  ──► Static segment tree or offline tricks.
│
└── Yes ─► Do you need range UPDATES or min/max/custom merges?
           ├── No (sums + point updates only) ──► Fenwick tree.
           └── Yes ──► Do elements get inserted/deleted in the middle?
                       ├── Yes ──► Augmented balanced BST (treap, etc.).
                       └── No  ──► Segment tree (lazy if range updates).
                                   Indexes huge and sparse? Compress them
                                   offline or use a dynamic tree online.

Segment tree vs Fenwick tree

A Fenwick tree, also called a binary indexed tree (BIT), was published by Peter Fenwick in 1994 in Software: Practice and Experience, where he used it to maintain cumulative symbol frequencies for arithmetic data compression. (The same structure had been described a few years earlier by Boris Ryabko, which is why some sources credit both.) It stores partial sums in a clever array layout and supports prefix queries and point updates in O(log n).

• Pick Fenwick when you need prefix or range sums (or XOR) with point updates. It's about ten lines of code, uses n + 1 slots and is fast.
• Pick a segment tree when the operation isn't invertible (min, max, GCD), when you need lazy range updates with arbitrary query types, when you need to walk down the tree with a custom condition or when nodes store structs.

The deeper reason: a Fenwick tree answers [L, R] as prefix(R) - prefix(L - 1). That subtraction only makes sense if the operation has an inverse. Sum has subtraction. Min doesn't.

Segment tree vs sparse table

A sparse table precomputes answers for every range whose length is a power of two. For operations where overlapping is harmless (min, max, GCD, also called idempotent operations), any range query is answered by two overlapping precomputed ranges in O(1). But it can't handle updates at all. For static range-minimum queries with heavy query traffic, it is often the better choice.

Segment tree vs sqrt decomposition

Sqrt decomposition splits the array into blocks of about √n elements and keeps one aggregate per block. It's slower asymptotically (O(√n) per query), but it is very easy to write and adapt to strange operations. For n = 100,000, √n is about 316, which is often fast enough. It's a reasonable fallback when a segment tree's merge or lazy logic gets too complicated.

Segment tree vs balanced BST

An augmented balanced binary search tree (like a treap or a red-black tree with subtree aggregates) can do everything a segment tree does and support inserting or deleting elements in the middle of the sequence. A segment tree has a fixed shape, so inserting into the middle means rebuilding. The cost is much more complex code and worse constant factors.

Common Mistakes and Edge Cases

These are the bugs that show up again and again in segment tree code, in interviews and in real code reviews.

min[0,7] with identity 0:          2   ← correct
min[1,3] with identity 0:          0   ← wrong, should be 3
min[1,3] with identity MAX_VALUE:  3

query[3,3] without push:  3    ← stale leaf, the +10 never arrived
query[3,3] with push:    13

Testing a Segment Tree

Segment tree bugs tend to appear only for particular sizes or operation sequences, so hand-written test cases rarely catch them. The most effective technique is differential testing: run the same random operations against the segment tree and against a dumb brute-force array and compare every answer.

Random rnd = new Random(42);   // fixed seed so failures are reproducible
for (int iter = 0; iter < 2000; iter++) {
    int n = 1 + rnd.nextInt(40);            // small sizes, including n = 1 and odd sizes
    long[] ref = new long[n];
    for (int i = 0; i < n; i++) ref[i] = rnd.nextInt(20);
    SegmentTree st = new SegmentTree(ref.clone());

    for (int op = 0; op < 60; op++) {
        int l = rnd.nextInt(n), r = rnd.nextInt(n);
        if (l > r) { int t = l; l = r; r = t; }
        if (rnd.nextBoolean()) {
            long v = rnd.nextInt(20);
            ref[l] = v;
            st.update(l, v);
        } else {
            long expected = 0;
            for (int i = l; i <= r; i++) expected += ref[i];
            if (st.query(l, r) != expected) {
                throw new AssertionError("mismatch at iteration " + iter);
            }
        }
    }
}

Small arrays are intentional. They hit edge cases like n = 1, odd sizes and ranges touching both ends far more often than large arrays do. A fixed random seed makes any failure reproducible. This is the same approach used to verify every implementation in this article: the recursive, iterative, lazy and dynamic trees, plus the k-th element descent, were each checked over thousands of random operation sequences on sizes from 1 to 40.

One honest lesson from writing this article: the code was never the problem, the hand-drawn diagrams were. An early draft of the lazy propagation diagram showed [0,3] = 59 instead of 52. The tests didn't catch it because tests don't read diagrams. Hand-tracing every number in every example did. If you write about data structures or explain one on a whiteboard, recompute each node from its children before you trust the picture.

Segment Trees in Production Systems

Most production code never hand-writes a segment tree. Databases, time-series stores and analytics engines already answer range aggregates with indexes and pre-aggregated rollups and those are the right first choice for persistent data. A segment tree makes sense when the data lives in memory, changes frequently and needs low-latency range answers that a database round trip can't provide.

Illustrative scenarios

These are realistic designs, not claims about how any specific company works:

• Seat or slot allocation. A booking service keeps a count tree of free slots per index and uses the descent trick to find "the k-th free seat" or "the first block with enough free capacity" in O(log n).
• Live min/max over a sliding history. A trading or monitoring dashboard keeps the last N price ticks in a circular buffer with a min/max segment tree, so "lowest price in the last 10 minutes" stays fast as new ticks overwrite old ones.
• Leaderboards by score bucket. A game backend keeps counts per score bucket. "How many players scored between 1,200 and 1,500?" is a range sum and "what is the score at the 90th percentile?" is a descent query.

Performance and memory

• A recursive tree of long values uses 4n × 8 bytes. For 10 million elements that is about 320 MB. The iterative 2n layout halves that to about 160 MB.
• Flat arrays are friendly to CPU caches. A pointer-based dynamic tree pays for object headers and scattered memory access. On a typical 64-bit JVM with compressed references, each small Node object like the one above takes around 32 bytes.
• Rebuilding is O(n). If the tree is derived from a database or a log, rebuilding on startup is usually simpler and safer than serializing the tree itself.

Concurrency

A segment tree is not thread-safe. A point update writes O(log n) nodes and a concurrent reader can see some ancestors updated and others not, which gives answers that never matched any real state of the array. Common options:

• A single lock (or ReentrantReadWriteLock when reads dominate). Simple and often enough because each operation is very short.
• A single writer thread that owns the tree, with requests sent through a queue. This avoids locks and keeps ordering explicit.
• Copy-on-write with a persistent tree. The writer builds a new version by copying O(log n) nodes and then publishes the new root with one atomic reference swap. Readers always see a complete, consistent snapshot. The cost is extra allocation and garbage collection pressure.
• Sharding by range. Split the index space into independent trees with separate locks. Queries that cross shards combine partial results, which works for any associative merge.

Security and input validation

If indexes or ranges come from API requests, validate them before touching the tree. Out-of-range indexes cause exceptions and in a dynamic segment tree an attacker who controls indexes can force node creation on every call, about 31 new nodes per update for a range of 10⁹, which can grow memory without bound. Cap the allowed index range, rate-limit updates and set a maximum node count.

Reliability and observability

• Track query and update latency percentiles. A sudden latency jump often means the tree grew larger than expected or lock contention increased.
• For dynamic trees, export the node count as a metric and alert on unexpected growth.
• Keep the differential tests in CI. Most segment tree bugs are logic bugs that pass simple tests.
• If the tree mirrors a source of truth, periodically compare a few random range answers against that source to detect drift.

When not to use a segment tree

My honest default: reach for the simplest structure that answers the question and only write a segment tree when that structure runs out. A segment tree is easy to get almost right and almost-right range code is worse than slower correct code. Specifically:

• The data never changes. Use prefix sums or a sparse table for min/max.
• You only need sums with point updates. A Fenwick tree is shorter and lighter.
• The data already lives in a database and query latency of a few milliseconds is acceptable. Use indexes and aggregate queries.
• You need inserts and deletes in the middle of the sequence. Use a balanced BST with augmentation or a rope.
• The query can't be expressed as an associative merge (median, mode, distinct count). Use a specialized variant or a different approach entirely.

Where Segment Trees Show Up

Documented uses in algorithms

• Area of a union of rectangles (Klee's measure problem in 2D). A sweep line moves across the x-axis. A segment tree over compressed y-coordinates tracks how much of the y-axis is currently covered. Each rectangle adds an interval when its left edge is passed and removes it at the right edge. This gives an O(n log n) algorithm and Bentley's original segment tree work was motivated by exactly this family of problems.
• Counting inversions and "smaller elements after self". Process the array from right to left and keep counts of seen values in a tree over compressed values.
• Skyline and interval scheduling problems, where you need the maximum height or booking count over a range with updates.

Well-known interview and practice problems

These LeetCode problems are commonly solved with a segment tree (often among other valid approaches):

• 307. Range Sum Query - Mutable (the canonical starting point; a Fenwick tree also works)
• 315. Count of Smaller Numbers After Self
• 218. The Skyline Problem
• 699. Falling Squares
• 715. Range Module
• 732. My Calendar III
• 850. Rectangle Area II

Segment Tree Interview Questions

Segment trees come up in coding interviews at companies that ask harder data structure questions and much more often in competitive programming. Interviewers usually care less about memorized code and more about whether you can explain the three overlap cases, justify the complexity and decide when a simpler structure would do.

FAQ

Summary

A segment tree stores precomputed answers for halves, quarters, eighths and so on of an array, so any range can be answered by combining a few stored values. That one idea gives you O(log n) queries and updates for any associative operation. Lazy propagation extends it to range updates and the dynamic, persistent and merge sort variants stretch it to huge index spaces, old versions and order statistics.

If you remember one thing, make it the checklist rather than the code: the data changes, the questions are about ranges and two halves can be combined into a whole. When all three hold, a segment tree is usually the right call. When one fails, there's almost always something simpler. And whatever you write, test it against a brute-force loop on small random inputs, including n = 6.