Segment Tree

A segment tree is a hierarchical data structure for answering range queries while supporting updates efficiently. Instead of recomputing an entire range after every change, the tree stores aggregate information for nested intervals, giving logarithmic query and update behavior.

Interval Decomposition

Every tree node represents an interval. Its children divide that interval into two smaller ranges until leaves represent individual elements.

Range Aggregation

Nodes can store sums, minimums, maximums, GCDs or other associative aggregates. A query combines only nodes whose intervals contribute to the requested range.

Point Updates

Changing one array value affects only the leaf for that position and its ancestors, so only logarithmically many nodes need recomputation.

When to Use It

Segment trees are valuable when range queries and updates are interleaved. Static prefix sums are simpler when the underlying values never change.

Worked Examples

Example 1: Build a Sum Segment Tree

Build recursively stores each leaf value and combines child sums into parent intervals.

Code

public class Main {
    static int[] tree;

    static void build(
        int[] nums,
        int node,
        int left,
        int right
    ) {
        if (left == right) {
            tree[node] = nums[left];
            return;
        }

        int mid =
            left + (right - left) / 2;

        build(nums, node * 2, left, mid);
        build(nums, node * 2 + 1, mid + 1, right);

        tree[node] =
            tree[node * 2]
            + tree[node * 2 + 1];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        tree = new int[4 * nums.length];

        build(nums, 1, 0, nums.length - 1);

        System.out.println(tree[1]);
    }
}

Expected Result

Example 2: Range Sum Query

Return zero for disjoint intervals, the stored aggregate for complete overlap and combine both children for partial overlap.

Code

public class Main {
    static int[] tree = {
        0, 10, 3, 7, 1, 2, 3, 4
    };

    static int query(
        int node,
        int left,
        int right,
        int ql,
        int qr
    ) {
        if (qr < left || right < ql) {
            return 0;
        }

        if (ql <= left && right <= qr) {
            return tree[node];
        }

        int mid =
            left + (right - left) / 2;

        return query(
                    node * 2,
                    left,
                    mid,
                    ql,
                    qr
               )
             + query(
                    node * 2 + 1,
                    mid + 1,
                    right,
                    ql,
                    qr
               );
    }

    public static void main(String[] args) {
        System.out.println(
            query(1, 0, 3, 1, 3)
        );
    }
}

Expected Result

Example 3: Point Update

Descend only into the child containing the changed index, then recompute ancestors while returning.

Code

public class Main {
    static int[] tree = new int[16];

    static void update(
        int node,
        int left,
        int right,
        int index,
        int value
    ) {
        if (left == right) {
            tree[node] = value;
            return;
        }

        int mid =
            left + (right - left) / 2;

        if (index <= mid) {
            update(
                node * 2,
                left,
                mid,
                index,
                value
            );
        } else {
            update(
                node * 2 + 1,
                mid + 1,
                right,
                index,
                value
            );
        }

        tree[node] =
            tree[node * 2]
            + tree[node * 2 + 1];
    }

    public static void main(String[] args) {
        update(1, 0, 3, 2, 8);
        System.out.println(tree[1]);
    }
}

Expected Result

Example 4: Tree Storage Size

Allocating roughly four times the input size is a common simple bound for an array-backed segment tree.

Code

public class Main {
    public static void main(String[] args) {
        int n = 100000;

        long[] tree =
            new long[4 * n];

        System.out.println(tree.length);
    }
}

Expected Result

Complexity Analysis

Operation	Complexity	Explanation
Build	O(n)	Every segment-tree node is constructed once.
Range query	O(log n) typical aggregate query	Only logarithmically many interval boundaries are traversed for standard range aggregation.
Point update	O(log n)	One root-to-leaf path is modified.
Storage	O(n)	The tree contains a linear number of nodes.

Common Mistakes

Using segment trees when immutable data makes prefix sums sufficient.
Mixing inclusive and exclusive range boundaries.
Returning the wrong identity value for a disjoint query.
Updating a leaf without recomputing its ancestors.

Interview Checklist

Define exactly what each node interval stores.
Choose the correct identity value for disjoint ranges.
Separate no-overlap, complete-overlap and partial-overlap query cases.
Consider lazy propagation only when range updates are actually required.