🌲 Segment Tree

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

---

✍️ 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

---

✅ 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.

📌 This is the final topic of our DSA Series! 🎉 🔗 DS Interview Prep Series
Thank you for following through. Whether you're revising or learning from scratch, I hope this series has helped solidify your understanding of core data structures.

If you find it helpful, feel free to share with peers, bookmark it for revision, or leave a ❤️ to support the effort.

🔗 Follow my blog on Hashnode: ns717.hashnode.dev
💼 Connect with me on LinkedIn: Nitin Singh

Thanks for reading, and happy coding! 💻🌳

---