Segment Trees

Segment Trees

You have an array of integers. An interviewer asks: “Answer range sum queries and handle point updates, both in O(log n).” A prefix sum array gives you O(1) queries but O(n) updates. A naive array gives you O(1) updates but O(n) queries. Neither achieves O(log n) for both. A segment tree does.

Segment trees are the go-to data structure whenever a problem demands both efficient range queries and efficient updates on a mutable array. They appear in competitive programming, database internals, computational geometry, and — critically — in interviews that test advanced data structure knowledge.

The Problem

Given an array arr[0..n-1], support two operations:

1. Range Query: compute an aggregate (sum, minimum, maximum, GCD) over a subarray arr[l..r].
2. Update: modify one or more elements and reflect the change in future queries.

Approach	Query	Point Update	Range Update
Naive array	O(n)	O(1)	O(n)
Prefix sum	O(1)	O(n) (rebuild)	O(n)
Segment tree	O(log n)	O(log n)	O(log n) with lazy

The segment tree balances both operations at O(log n), handling the general case where queries and updates are interspersed.

Tree Structure

A segment tree is a full binary tree where:

• Each leaf node stores a single array element.
• Each internal node stores the aggregate of its children’s ranges.
• The root covers the entire array [0, n-1].

For the array [1, 3, 5, 7, 9, 11], a sum segment tree looks like:

                [36]            covers [0,5]
              /      \
          [9]          [27]     covers [0,2] and [3,5]
         /   \        /    \
       [4]   [5]   [16]   [11]  covers [0,1],[2,2],[3,4],[5,5]
      / \          / \
    [1] [3]     [7] [9]         covers individual elements

Array Representation

Like heaps, segment trees use an array layout:

• Node at index i has children at 2*i + 1 and 2*i + 2.
• Size of the array: 4 × n (a safe upper bound that accounts for the tree not always being perfectly balanced at the leaf level).

Why 4n? The tree has at most 2n - 1 nodes for a perfectly sized array, but when n is not a power of 2, the array representation leaves gaps. Allocating 4n guarantees enough space without complex size calculations.

Building the Segment Tree

Build the tree bottom-up recursively. Each leaf gets an array element, and each internal node computes the aggregate of its children.

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

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

    private void build(int[] 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 + 1, start, mid);
        build(arr, 2 * node + 2, mid + 1, end);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

Time: O(n) — each of the 2n - 1 nodes is visited once. Space: O(n) for the tree array.

Range Sum Query

A range query on [l, r] walks the tree and encounters three cases at each node covering [start, end]:

1. Total overlap: [start, end] is entirely within [l, r] → return this node’s value.
2. No overlap: [start, end] is entirely outside [l, r] → return 0 (identity for sum).
3. Partial overlap: recurse into both children and combine results.

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

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

Time: O(log n). At every level of the tree, at most two nodes have partial overlap (one on the left boundary, one on the right). All other nodes are either fully inside or fully outside the range.

Range Minimum Query

Swap the aggregate function:

public int rangeMin(int l, int r) {
    return queryMin(0, 0, n - 1, l, r);
}

private int queryMin(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        return Integer.MAX_VALUE; // identity for min
    }
    if (l <= start && end <= r) {
        return tree[node];
    }
    int mid = start + (end - start) / 2;
    int leftMin = queryMin(2 * node + 1, start, mid, l, r);
    int rightMin = queryMin(2 * node + 2, mid + 1, end, l, r);
    return Math.min(leftMin, rightMin);
}

The structure is identical — only the merge operation and identity value change. This is the core insight behind making segment trees generic.

Point Update

To update arr[index] = value:

1. Find the leaf node corresponding to index.
2. Update its value.
3. Propagate the change upward — every ancestor recomputes its aggregate from its children.

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

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

Time: O(log n) — you traverse from root to leaf (height of the tree) and update one node per level on the way back up.

Range Update with Lazy Propagation

The Problem

Suppose you need to add a value to every element in a range [l, r]. With point updates, that costs O((r - l + 1) × log n) — updating each element individually. For large ranges, this is unacceptable.

The Lazy Idea

Instead of immediately updating every node in the range, defer the update. Store a “pending” value at each node. When a node’s range is entirely covered by the update range, mark it as lazy and move on. Only propagate (push down) the lazy value to children when a future query or update needs to access those children.

This is lazy propagation: do the minimum work now, and pay the cost later only when you need the result.

Implementation

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

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

    private void build(int[] 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 + 1, start, mid);
        build(arr, 2 * node + 2, mid + 1, end);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

    private void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = start + (end - start) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            tree[leftChild] += lazy[node] * (mid - start + 1);
            tree[rightChild] += lazy[node] * (end - mid);

            lazy[leftChild] += lazy[node];
            lazy[rightChild] += lazy[node];

            lazy[node] = 0;
        }
    }

    public void rangeUpdate(int l, int r, int value) {
        rangeUpdate(0, 0, n - 1, l, r, value);
    }

    private void rangeUpdate(int node, int start, int end, int l, int r, int value) {
        if (r < start || end < l) {
            return;
        }
        if (l <= start && end <= r) {
            tree[node] += value * (end - start + 1);
            lazy[node] += value;
            return;
        }
        pushDown(node, start, end);
        int mid = start + (end - start) / 2;
        rangeUpdate(2 * node + 1, start, mid, l, r, value);
        rangeUpdate(2 * node + 2, mid + 1, end, l, r, value);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

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

    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        pushDown(node, start, end);
        int mid = start + (end - start) / 2;
        int leftSum = query(2 * node + 1, start, mid, l, r);
        int rightSum = query(2 * node + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }
}

How pushDown Works

pushDown is the heart of lazy propagation:

1. Check if the current node has a pending lazy value.
2. Apply the lazy value to both children: update their tree values (accounting for range size) and propagate the lazy value to their lazy slots.
3. Clear the lazy value at the current node.

You call pushDown before recursing into children during both queries and updates. This ensures that by the time you reach a node, all its ancestors’ pending updates have already been applied.

Time: O(log n) for both rangeUpdate and rangeSum. The lazy mechanism ensures that at most O(log n) nodes are visited per operation.

Generic Segment Tree

For interview flexibility, here is a segment tree parameterized by the merge operation:

public class GenericSegmentTree {
    private final long[] tree;
    private final int n;
    private final LongBinaryOperator merge;
    private final long identity;

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

    private void build(int[] 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 + 1, start, mid);
        build(arr, 2 * node + 2, mid + 1, end);
        tree[node] = merge.applyAsLong(tree[2 * node + 1], tree[2 * node + 2]);
    }

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

    private long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return identity;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        long leftResult = query(2 * node + 1, start, mid, l, r);
        long rightResult = query(2 * node + 2, mid + 1, end, l, r);
        return merge.applyAsLong(leftResult, rightResult);
    }

    public void update(int index, long value) {
        update(0, 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 + 1, start, mid, index, value);
        } else {
            update(2 * node + 2, mid + 1, end, index, value);
        }
        tree[node] = merge.applyAsLong(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

Usage:

int[] arr = {1, 3, 5, 7, 9, 11};

// Range Sum
var sumTree = new GenericSegmentTree(arr, Long::sum, 0);

// Range Min
var minTree = new GenericSegmentTree(arr, Math::min, Long.MAX_VALUE);

// Range Max
var maxTree = new GenericSegmentTree(arr, Math::max, Long.MIN_VALUE);

// Range GCD
var gcdTree = new GenericSegmentTree(arr, (a, b) -> gcd(a, b), 0);

The LongBinaryOperator and identity parameters let you swap the aggregate function without rewriting the tree structure. The identity value is what gets returned for non-overlapping ranges — 0 for sum, MAX_VALUE for min, MIN_VALUE for max, 0 for GCD.

Comparison: Segment Tree vs Fenwick Tree vs Sparse Table

Feature	Segment Tree	Fenwick Tree (BIT)	Sparse Table
Build time	O(n)	O(n log n)	O(n log n)
Point query	O(log n)	O(log n)	O(1)
Range query	O(log n)	O(log n)	O(1)
Point update	O(log n)	O(log n)	Not supported
Range update	O(log n) with lazy	O(log n) with tricks	Not supported
Supported operations	Any associative	Prefix-decomposable (sum, XOR)	Idempotent (min, max, GCD)
Lazy propagation	Yes	No	No
Memory	4n	n	n log n
Implementation complexity	Moderate	Low	Low

Use a Segment Tree when you need range updates (especially with lazy propagation), or when the merge operation is not prefix-decomposable (like min/max updates with range queries).

Use a Fenwick Tree when the operation is prefix-decomposable (sum, XOR) and you only need point updates. It uses less memory, runs faster in practice due to lower constants, and is easier to implement.

Use a Sparse Table when the array is static (no updates) and you need O(1) range queries for idempotent operations like min or max. The O(n log n) preprocessing cost pays for itself when queries vastly outnumber modifications.

Classic Interview Problems

Range Sum Query — Mutable (LeetCode 307)

This is the textbook segment tree application:

class NumArray {
    private final SegmentTree segTree;
    private final int n;

    public NumArray(int[] nums) {
        this.n = nums.length;
        this.segTree = new SegmentTree(nums);
    }

    public void update(int index, int val) {
        segTree.update(index, val);
    }

    public int sumRange(int left, int right) {
        return segTree.rangeSum(left, right);
    }
}

Interviewers want to see that you recognize the need for a segment tree (or Fenwick tree) the moment you hear “range sum” combined with “update.” The prefix sum approach fails because updates require O(n) rebuilding.

Count of Smaller Numbers After Self

Problem: given an array nums, return a list where result[i] is the count of elements to the right of nums[i] that are smaller than nums[i].

Segment tree approach: process the array from right to left. Maintain a segment tree over the value range. For each element, query the range [0, nums[i] - 1] to count how many smaller values have been seen, then update the tree to include nums[i].

public List<Integer> countSmaller(int[] nums) {
    int offset = 10001; // shift values to positive range
    int size = 2 * offset + 2;
    int[] tree = new int[4 * size];
    var result = new LinkedList<Integer>();

    for (int i = nums.length - 1; i >= 0; i--) {
        int shiftedVal = nums[i] + offset;
        int count = query(tree, 0, 0, size - 1, 0, shiftedVal - 1);
        result.addFirst(count);
        update(tree, 0, 0, size - 1, shiftedVal);
    }
    return result;
}

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

private int query(int[] tree, int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = start + (end - start) / 2;
    return query(tree, 2 * node + 1, start, mid, l, r)
         + query(tree, 2 * node + 2, mid + 1, end, l, r);
}

Time: O(n log M) where M is the value range. This can also be solved with a modified merge sort, but the segment tree approach generalizes to other counting problems.

Edge Cases and Interviewer Tips

• Empty array: your constructor should handle n = 0 gracefully. A segment tree over an empty array should return the identity value for any query.
• Single element: queries on [0, 0] should return that element. Updates should work without out-of-bounds errors.
• Invalid ranges: if l > r, return the identity value. Defensive checks here prevent subtle bugs.
• Array size: allocate 4 * n for the tree array, not 2 * n or 2 * n + 1. Underallocation causes array index out of bounds on non-power-of-2 inputs.
• 0-indexed vs 1-indexed: be consistent. The implementation above uses 0-indexed arrays and 0-indexed tree nodes. Some references use 1-indexed trees (where children of node i are at 2*i and 2*i + 1). Pick one and stick with it.
• Overflow: for sum queries on large arrays with large values, use long instead of int.
• Lazy propagation pitfalls: forgetting to call pushDown before recursing is the most common bug. Every query and every update that recurses into children must push down pending lazy values first.
• When to use vs alternatives: if the interviewer asks “can you do this with a simpler structure?” — mention Fenwick trees for prefix sums and sorted arrays for static datasets. Show that you understand the trade-offs, not that a segment tree is your only hammer.

Segment trees are advanced data structures. When you reach for one in an interview, explain why — specifically, that you need O(log n) for both queries and updates, and that simpler structures cannot provide both. This reasoning demonstrates that your choice is deliberate, not default.