Segment Tree

The Powerhouse for Range Queries

From range sum queries to finding minimums in subarrays, Segment Trees are one of the most powerful and flexible data structures for tackling interval problems efficiently.

🧠 Introduction

A Segment Tree is a binary tree used for storing information about intervals, or segments. It allows querying and updating over a range of elements in O(log n) time, making it ideal for problems involving:

• Range Sum Queries

• Range Minimum/Maximum Queries

• Frequency Count in Ranges

• Lazy Propagation for Range Updates

---

🔍 Why Not Naive Solutions?

Say you want to find the sum of elements in a subarray multiple times. A brute-force approach will take O(n) time per query — inefficient for large datasets.

With a Segment Tree:

• Building the tree takes O(n)

• Each query/update runs in O(log n)

---

🧩 How Segment Tree Works

Segment Tree divides the array into segments (intervals), storing aggregated data (like sum, min, max) at each node.

Key Concepts:

• Leaf nodes represent individual elements.

• Internal nodes represent merged results of their child segments.

• The root represents the entire range.

---

⚙️ Operations

1. Build

• Description: Construct the segment tree from an array

• Time Complexity: O(n)

2. Query

• Description: Find a value in a range (e.g., sum, min, max)

• Time Complexity: O(log n)

3. Update

• Description: Update a single element or a range

• Time Complexity: O(log n)

---

✍️ Java Code Example

class SegmentTree 
{
    int[] tree;
    int n;

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

    void build(int[] arr, int start, int end, int index) 
   {
        if (start == end) 
        {
            tree[index] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, start, mid, 2 * index + 1);
        build(arr, mid + 1, end, 2 * index + 2);
        tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
    }

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

    int queryUtil(int start, int end, int l, int r, int index) 
    {
        if (r < start || l > end) return 0;
        if (l <= start && end <= r) return tree[index];
        int mid = (start + end) / 2;
        return queryUtil(start, mid, l, r, 2 * index + 1) +
               queryUtil(mid + 1, end, l, r, 2 * index + 2);
    }

    void update(int pos, int val) 
    {
        updateUtil(0, n - 1, pos, val, 0);
    }

    void updateUtil(int start, int end, int pos, int val, int index)  
    {
        if (start == end) 
       {
            tree[index] = val;
            return;
        }
        int mid = (start + end) / 2;
        if (pos <= mid) 
        {
            updateUtil(start, mid, pos, val, 2 * index + 1);
        }
        else
        {
            updateUtil(mid + 1, end, pos, val, 2 * index + 2);
        }
        tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
    }
}

---

🔁 Real-World Analogy

Imagine managing a spreadsheet where each row represents data over time. Instead of recalculating totals every time someone filters by month or week, a Segment Tree pre-aggregates those totals so you can respond in milliseconds.

---

🧠 LeetCode Practice Problems

1. Range Sum Query - Immutable – Easy – LeetCode#303

2. Range Sum Query 2D - Immutable – Medium – LeetCode#304

3. Range Sum Query - Mutable – Medium – LeetCode#307

4. Count of Smaller Numbers After Self – Hard – LeetCode#315

5. Maximum Sum Queries – Hard – LeetCode#2736

---

✅ Tips for Interview

• Corner Cases: Don’t forget to handle edge conditions like out-of-bound indices or overlapping intervals.

• Variants: Learn both iterative and recursive implementations.

• Lazy Propagation: Know this for range updates—it often shows up in advanced problems.

• Know when to use it: Prefer Segment Tree over Binary Indexed Tree (Fenwick Tree) when updates/queries are more complex (e.g., min/max or range update).

---

🔚 Wrapping Up

Segment Trees are powerful tools in any coder's toolkit—especially for range-based problems that require frequent updates or queries. They provide fast, elegant solutions and are widely applicable in competitive programming and system design.

Happy coding! 🚀

Nitin
Hashnode | Substack | LinkedIn | GIT | Youtube | Instagram