Segment Tree Data Structure

A Segment Tree is a versatile data structure used to perform range queries and updates efficiently. It allows us to process operations like Range Sum Query or Range Minimum/Maximum Query in $O(\log N)$ time, significantly faster than the $O(N)$ brute-force approach.

The Intuition

A Segment Tree is a binary tree where:

1. Each leaf node represents a single element from the original array.
2. Each internal node represents the combined result (sum, min, max, etc.) of its children's segments.

Java Implementation (Range Sum Query)

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

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 1, 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) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public 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];
        
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, L, R) + query(2 * node + 1, mid + 1, end, L, R);
    }
}

Why it matters

• Range Queries: Efficiently querying sum, minimum, or maximum over a range $[L, R]$.
• Dynamic Updates: Updating array elements in $O(\log N)$ time.

Complexity

• Time: O(log N) for both query and update.
• Space: O(N) to store the tree (typically 4 * N).