Segment Trees

1. Introduction: The Range Query Problem

Imagine you have an array of 100,000 numbers representing daily stock prices. A user wants to know the Maximum stock price between Day 10 and Day 50,000.

• If you scan the array, it takes $O(N)$ time.
• If the user asks 100,000 questions (queries), it takes $O(N \times Q) = 10^{10}$ operations. Your server crashes.

"Wait," you say, "I know the Prefix Sum pattern! I can pre-calculate the sums/maxes!" Prefix Sums work brilliantly ($O(1)$ query time)... until the array changes. What if the stock price on Day 15 updates? To fix your Prefix Sum array, you have to recalculate everything from Day 15 to Day 100,000. Point Updates on a Prefix Sum array take $O(N)$ time.

The Segment Tree solves this dilemma. It is a highly specialized Binary Tree that allows you to perform Range Queries (Sum, Max, Min) in $O(\log N)$ time AND Point Updates in $O(\log N)$ time. It is the ultimate compromise between fast reads and fast writes.

2. Core Concept: The Tree of Intervals

A Segment Tree is a perfectly balanced binary tree where every node represents a specific interval (range) of the original array.

• The Root Node represents the entire array [0, N-1].
• Its Left Child represents the left half [0, mid].
• Its Right Child represents the right half [mid+1, N-1].
• The Leaf Nodes represent a single index [i, i].

Because the tree divides the array in half at every level, its height is exactly $\lceil \log_2 N \rceil$. Like a Priority Queue (Heap), we don't need to build actual Node objects with pointers! Because it is a complete binary tree, we can map it perfectly onto a flat integer array of size $4N$.

3. Advanced Code Example: Building and Querying (Range Sum)

Problem Statement: (LeetCode 307) Range Sum Query - Mutable. Given an integer array nums, handle multiple queries of the following types:

1. update(index, val): Updates the value of nums[index] to be val.
2. sumRange(left, right): Returns the sum of the elements in nums between indices left and right.

public class NumArray {
    int[] tree;
    int n;

    public NumArray(int[] nums) {
        n = nums.length;
        if (n > 0) {
            // A segment tree array requires at most 4N space
            tree = new int[n * 4];
            buildTree(nums, 0, 0, n - 1);
        }
    }

    // 1. BUILD THE TREE: O(N)
    private void buildTree(int[] nums, int treeIndex, int lo, int hi) {
        if (lo == hi) {
            // Leaf node: stores the actual array value
            tree[treeIndex] = nums[lo];
            return;
        }
        
        int mid = lo + (hi - lo) / 2;
        int leftChildIndex = 2 * treeIndex + 1;
        int rightChildIndex = 2 * treeIndex + 2;
        
        // Recursively build left and right subtrees
        buildTree(nums, leftChildIndex, lo, mid);
        buildTree(nums, rightChildIndex, mid + 1, hi);
        
        // The current node's value is the sum of its children
        tree[treeIndex] = tree[leftChildIndex] + tree[rightChildIndex];
    }

    // 2. POINT UPDATE: O(log N)
    public void update(int index, int val) {
        updateTree(0, 0, n - 1, index, val);
    }
    
    private void updateTree(int treeIndex, int lo, int hi, int arrIndex, int val) {
        if (lo == hi) { // Found the exact leaf node
            tree[treeIndex] = val;
            return;
        }
        
        int mid = lo + (hi - lo) / 2;
        int leftChildIndex = 2 * treeIndex + 1;
        int rightChildIndex = 2 * treeIndex + 2;
        
        // If the target index is in the left half, go left. Else go right.
        if (arrIndex <= mid) {
            updateTree(leftChildIndex, lo, mid, arrIndex, val);
        } else {
            updateTree(rightChildIndex, mid + 1, hi, arrIndex, val);
        }
        
        // As we backtrack up the tree, recalculate the sums!
        tree[treeIndex] = tree[leftChildIndex] + tree[rightChildIndex];
    }

    // 3. RANGE QUERY: O(log N)
    public int sumRange(int left, int right) {
        return queryTree(0, 0, n - 1, left, right);
    }
    
    private int queryTree(int treeIndex, int lo, int hi, int qLeft, int qRight) {
        // Condition 1: Perfect overlap. This node perfectly represents the requested range.
        if (qLeft == lo && qRight == hi) {
            return tree[treeIndex];
        }
        
        int mid = lo + (hi - lo) / 2;
        int leftChildIndex = 2 * treeIndex + 1;
        int rightChildIndex = 2 * treeIndex + 2;
        
        // Condition 2: Partial overlap. We must dig deeper.
        if (qRight <= mid) {
            // The entire query is inside the left child
            return queryTree(leftChildIndex, lo, mid, qLeft, qRight);
        } else if (qLeft > mid) {
            // The entire query is inside the right child
            return queryTree(rightChildIndex, mid + 1, hi, qLeft, qRight);
        } else {
            // The query splits across both children! 
            // e.g., query [2, 5], but mid is 3. We query [2, 3] on left, and [4, 5] on right.
            return queryTree(leftChildIndex, lo, mid, qLeft, mid) + 
                   queryTree(rightChildIndex, mid + 1, hi, mid + 1, qRight);
        }
    }
}

4. Concept: Lazy Propagation

If you need to update an entire range at once (e.g., updateRange(3, 1000, +5), adding 5 to all elements between index 3 and 1000), calling our update() function 998 times will take $O(Q \log N)$ time. To do range updates in strict $O(\log N)$ time, we use Lazy Propagation.

When a range update perfectly matches a Segment Tree node, we update that node's value immediately, but we DO NOT update its children. Instead, we write a "Lazy Note" on the node (e.g., lazy[treeIndex] = 5). In future queries, if we ever need to visit those children, we read the lazy note, push the +5 down to the children, and clear the note. This delays massive $O(N)$ tree updates until they are absolutely necessary, preserving $O(\log N)$ performance.

(Note: Lazy Propagation is a highly advanced competitive programming concept, rarely required in standard FAANG interviews unless interviewing for an L5/L6 algorithmic specialist role).

5. Alternative: Binary Indexed Tree (Fenwick Tree)

A Segment Tree requires $4N$ space and involves complex recursive boundaries. For simple Range Sum problems (no Range Min or Range Max), a Fenwick Tree (Binary Indexed Tree / BIT) is heavily preferred in interviews.

A Fenwick Tree uses bitwise operations (i & -i) to jump through an array. It achieves the exact same $O(\log N)$ query and $O(\log N)$ update, but only requires $1N$ space and can be written in 10 lines of code! However, it is mathematically dense and ONLY works for operations that can be "reversed" (like Addition/Subtraction). It does not work for Range Min/Max.

6. Common Mistakes Beginners Make

1. Allocating an array of size N instead of 4N

   • The Mistake: tree = new int[n];
   • Why it's wrong: A complete binary tree for $N$ leaf nodes requires roughly $2N$ nodes. However, because $N$ is rarely a perfect power of 2, the bottom level of the array-mapped tree will have massive gaps. The mathematical worst-case requirement for the array size is precisely $4N$. If you use $2N$, you will hit an ArrayIndexOutOfBoundsException.

2. Incorrect Splitting during Queries

   • The Mistake:

   return queryTree(leftChild, lo, mid, qLeft, qRight) + 
          queryTree(rightChild, mid + 1, hi, qLeft, qRight);
   

   • Why it's wrong: If you blindly pass the full [qLeft, qRight] to the left child, and part of that query belongs to the right side, the left child's boundaries will get confused. When a query splits across the middle, you MUST clamp the boundaries: query the left child from [qLeft, mid], and the right child from [mid + 1, qRight].

3. Using Segment Trees for Static Arrays

   • The Mistake: Writing a 50-line Segment Tree when the array never changes.
   • Why it's wrong: If there are no point updates, Prefix Sums solve Range Sum queries in $O(1)$ time with 5 lines of code. Segment Trees are explicitly designed for MUTABLE arrays.

7. Interview Q&A

Q1: How does a Segment Tree find the Minimum value in a range? Answer: The structure is identical to the Range Sum tree. The only difference is the aggregation logic. When building or updating, instead of tree[node] = left + right, you use tree[node] = Math.min(left, right). When querying, if the query splits across both children, you return the min of the two recursive calls.

Q2: What is the Time Complexity to build a Segment Tree? Answer: $O(N)$. Even though we recursively divide by 2, we visit exactly $2N - 1$ nodes to fill the tree. This is a strict linear scan.

Q3: Can a Segment Tree handle adding new elements to the array (changing N)? Answer: No. Standard Segment Trees require a fixed-size universe $N$ because the $4N$ array is pre-allocated and the midpoints are mathematically fixed. If you need to dynamically append elements to the end of the array, you must use a Dynamic Segment Tree (which uses actual Node pointers instead of an array) or a self-balancing BST (like a Red-Black Tree or Treap).

8. Practice Problems

1. Range Sum Query - Mutable (LeetCode 307)
   • Goal: Write the standard array-based Segment Tree perfectly.
2. Count of Smaller Numbers After Self (LeetCode 315)
   • Hint: Can be solved beautifully with a Segment Tree tracking frequencies, though Merge Sort is also common.
3. Falling Squares (LeetCode 699 - Hard)
   • Hint: Requires a Segment Tree with Lazy Propagation for Range Max queries!

9. Summary

• The Tradeoff: Prefix Sums are $O(1)$ read, $O(N)$ write. Segment Trees are $O(\log N)$ read, $O(\log N)$ write.
• The Structure: A Segment Tree is an array of size $4N$.
• The Core Trick: Every node represents an interval [lo, hi]. If a query perfectly overlaps [lo, hi], return the node immediately without traversing deeper.
• When to use: Mutable array range queries.

Advanced Code Implementations

// Example: Segment Tree Build and Range Sum Query
public class SegmentTree {
    int[] tree;
    int n;
    
    public SegmentTree(int[] nums) {
        if (nums.length > 0) {
            n = nums.length;
            tree = new int[n * 2];
            buildTree(nums);
        }
    }
    
    private void buildTree(int[] nums) {
        for (int i = n, j = 0; i < 2 * n; i++, j++)
            tree[i] = nums[j];
        for (int i = n - 1; i > 0; i--)
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
    
    public void update(int pos, int val) {
        pos += n;
        tree[pos] = val;
        while (pos > 0) {
            int left = pos, right = pos;
            if (pos % 2 == 0) right = pos + 1;
            else left = pos - 1;
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }
    }
    
    public int sumRange(int l, int r) {
        l += n;
        r += n;
        int sum = 0;
        while (l <= r) {
            if ((l % 2) == 1) sum += tree[l++];
            if ((r % 2) == 0) sum += tree[r--];
            l /= 2;
            r /= 2;
        }
        return sum;
    }
}

// Example: Fenwick Tree (Binary Indexed Tree) Alternative
public class FenwickTree {
    int[] bit;
    int n;
    
    public FenwickTree(int size) {
        this.n = size;
        bit = new int[n + 1];
    }
    
    public void update(int i, int delta) {
        i++;
        while (i <= n) {
            bit[i] += delta;
            i += i & (-i);
        }
    }
    
    public int query(int i) {
        i++;
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & (-i);
        }
        return sum;
    }
}

Expanded Interview Q&A

Q1: What is the main use case for a Segment Tree?

Answer: Answering range queries (like sum, min, max) and updating array elements in logarithmic time O(log N).

Q2: Why is a Segment Tree array typically sized 2 * N or 4 * N?

Answer: A perfectly balanced binary tree with N leaves will have 2N - 1 nodes. If represented iteratively, 2*N suffices. For a recursive segment tree, 4*N is safely bounded.

Q3: What is the difference between a Segment Tree and a Fenwick Tree (BIT)?

Answer: Fenwick Trees are easier to code, use less memory (N), and are faster in practice for cumulative sums. Segment Trees are more flexible (can do range min/max, which BIT struggles with).

Q4: How does Lazy Propagation help in Segment Trees?

Answer: It allows you to perform range updates in O(log N) instead of O(N) by deferring updates to child nodes until they are actually queried.

Q5: What is the time complexity of building a Segment Tree?

Answer: O(N), because each node represents an interval and there are at most 2N nodes to compute.