Segment Tree Range Queries

Reference for point update + range query problems. Java has no built-in segment tree — use this template and read .sum, .max, or .min from the query result.

Related: 17-my-calendar-iii.md solves calendar peak overlap with a sweep line. Use a segment tree when you need O(log n) point updates and range queries on a dense index range.

When to use

Use a segment tree when operations are online (many updates and queries) and re-scanning the array each time is too slow.

Core idea

• Binary tree over array indices — each node covers interval [l, r]
• Each node stores an aggregate of its segment (here: sum, max, min)
• Query [ql, qr]: recurse; fully covered node → return its aggregate; no overlap → return neutral; partial → merge left + right results
• Point update: recurse to the target leaf, then merge back up the path

Query cases

Case 1 — total overlap:  ql <= l && r <= qr  →  return tree[index]
Case 2 — no overlap:      r < ql || l > qr    →  return Node.neutral()
Case 3 — partial overlap: recurse both children → Node.merge(left, right)

Both query and update are O(log n).

Java Solution — Segment Tree Template

class SegmentTree {

    static class Node {
        int sum, max, min;

        Node(int sum, int max, int min) {
            this.sum = sum;
            this.max = max;
            this.min = min;
        }

        static Node neutral() {
            return new Node(0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        static Node merge(Node left, Node right) {
            return new Node(
                left.sum + right.sum,
                Math.max(left.max, right.max),
                Math.min(left.min, right.min)
            );
        }
    }

    private Node[] tree;
    private int n;

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

    private void buildTree(int[] input, int index, int l, int r) {
        if (l == r) {
            tree[index] = new Node(input[l], input[l], input[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        buildTree(input, 2 * index + 1, l, mid);
        buildTree(input, 2 * index + 2, mid + 1, r);
        tree[index] = Node.merge(tree[2 * index + 1], tree[2 * index + 2]);
    }

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

    private Node query(int index, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tree[index];
        }
        if (r < ql || l > qr) {
            return Node.neutral();
        }
        int mid = l + (r - l) / 2;
        Node leftResult = query(2 * index + 1, l, mid, ql, qr);
        Node rightResult = query(2 * index + 2, mid + 1, r, ql, qr);
        return Node.merge(leftResult, rightResult);
    }

    public void update(int targetIdx, int newValue) {
        update(0, 0, n - 1, targetIdx, newValue);
    }

    private void update(int index, int l, int r, int targetIdx, int newValue) {
        if (l == r) {
            tree[index] = new Node(newValue, newValue, newValue);
            return;
        }
        int mid = l + (r - l) / 2;
        if (targetIdx <= mid) {
            update(2 * index + 1, l, mid, targetIdx, newValue);
        } else {
            update(2 * index + 2, mid + 1, r, targetIdx, newValue);
        }
        tree[index] = Node.merge(tree[2 * index + 1], tree[2 * index + 2]);
    }
}

Why Node.neutral() matters

Partial queries only hit one side of the tree. The untouched side must not pollute the merge — sum = 0, max = -∞, min = +∞ keeps Node.merge correct.

Example — Range Sum Query Mutable (LC 307)

LeetCode 307 — point update, range sum query. Use .sum from the query result.

class NumArray {
    private final SegmentTree st;

    public NumArray(int[] nums) {
        st = new SegmentTree(nums);
    }

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

    public int sumRange(int left, int right) {
        return st.query(left, right).sum;
    }
}

Need range max or min on the same array? Same tree — use .max or .min:

int rangeMax = st.query(left, right).max;
int rangeMin = st.query(left, right).min;

Example — Range Max Query

Same template, no code changes — only read a different field:

// max in nums[left..right]
int ans = st.query(left, right).max;

Problems like “max in range after point updates” use the identical tree.

Cheat sheet

For range add over [l, r] (many cells at once), this template needs lazy propagation — out of scope here; use sweep line (#17) when that fits instead.

Why It Teaches You Something

One segment tree answers sum, max, and min — the only change at call sites is which field you read. The pattern to memorize:

1. Build — leaf = single element, internal = Node.merge(children)
2. Query — total overlap / no overlap / partial merge
3. Update — walk to leaf, merge back up

That skeleton covers most interview segment tree problems that use point update + range query.