Chapter 47 -Segment Trees: The Final Chapter of My DSA Journey

Hey everyone! 🎉

I’m thrilled to share that this is the last chapter in my DSA with Java series! It’s been an incredible journey, and I’m excited to wrap it up with an important topic: Segment Trees. Segment trees are a powerful data structure, used widely for efficiently solving range queries. Here, I’ll walk you through everything you need to know about them. Let’s dive in!

---

1. 🌟 Segment Tree Introduction

To start, Segment Trees are a type of binary tree that allows for efficient range-based queries and updates. They’re commonly used for problems where you need to find the sum, minimum, maximum, or other aggregated data within a range of an array.

Key Advantages of Segment Trees

• Efficient Query Handling: Segment trees allow you to query a range in O(log N) time, making them much faster than looping through every element in that range.

• Flexible Structure: You can customize the tree to perform different operations (sum, max, min, etc.).

Imagine you have an array [1, 3, 5, 7, 9, 11], and you want to find the sum of different segments, like [3, 5, 7]. A segment tree helps you achieve this efficiently by storing aggregate values at each node.

---

2. 🔢 Counting and Meaning of Nodes in a Segment Tree

When building a segment tree, the structure generally follows this principle:

• Leaf Nodes: Represent individual elements from the array.

• Internal Nodes: Represent the aggregated value (sum, max, min) of a range of elements.

For an array of size N, a segment tree typically requires around 2 * (2^⌈log₂N⌉) - 1 nodes, where the height is the smallest power of two that’s greater than or equal to N.

---

3. 🛠 Building the Segment Tree

To construct the tree:

1. Divide the array into segments down to individual elements.

2. Combine elements in each segment to form parent nodes, building from the leaves upward to the root.

Java Code for Building a Segment Tree for Range Sum

class SegmentTree {
    int[] tree;
    int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[2 * n];
        buildTree(arr);
    }

    private void buildTree(int[] arr) {
        // Load leaves
        for (int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
        // Build the tree by combining nodes
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }
}

Complexity: The build process takes O(N) time.

---

4. 🔍 Performing Queries on the Segment Tree

Segment trees allow us to efficiently perform range queries. For example, in a range sum query, only relevant segments are accessed, allowing us to avoid looping through each element in the range.

Java Code for Range Sum Query

public int rangeQuery(int L, int R) {
    L += n; // Shift index to leaf level
    R += n;
    int sum = 0;
    while (L <= R) {
        if ((L % 2) == 1) sum += tree[L++]; // Right child
        if ((R % 2) == 0) sum += tree[R--]; // Left child
        L /= 2;
        R /= 2;
    }
    return sum;
}

Time Complexity: O(log N)

---

5. 🔄 Updating the Segment Tree

Segment trees also allow easy updates. When a node is updated, changes propagate up to the parent nodes to maintain the aggregate values.

Java Code for Updating an Element

public void update(int index, int value) {
    index += n;
    tree[index] = value;
    while (index > 1) {
        index /= 2;
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }
}

Time Complexity: O(log N)

---

6. 🔺 Max/Min Segment Tree (Creation)

To build a max or min segment tree, the tree nodes store the maximum or minimum of child nodes at each level. This allows for efficient max/min range queries.

Java Code for Building a Max Segment Tree

private void buildMaxTree(int[] arr) {
    for (int i = 0; i < n; i++) {
        tree[n + i] = arr[i];
    }
    for (int i = n - 1; i > 0; --i) {
        tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
    }
}

---

7. ❓ Max/Min Segment Tree (Query/Update)

For max/min segment trees, the query and update logic is similar to the sum segment tree.

Java Code for Max Range Query

public int rangeMaxQuery(int L, int R) {
    L += n;
    R += n;
    int max = Integer.MIN_VALUE;
    while (L <= R) {
        if ((L % 2) == 1) max = Math.max(max, tree[L++]);
        if ((R % 2) == 0) max = Math.max(max, tree[R--]);
        L /= 2;
        R /= 2;
    }
    return max;
}

Time Complexity: O(log N)

---

Wrapping Up: 🎉 Conclusion of the DSA with Java Series

With this final chapter, we’ve completed the DSA with Java series! Segment Trees are a powerful and flexible data structure that provides an efficient way to handle complex queries. Thank you for following along on this journey! I hope this series has helped you gain a solid foundation in Data Structures and Algorithms.

Stay Connected

If you’d like to stay connected and continue learning together, feel free to follow me on:

• LinkedIn

• GitHub

• LeetCode

Thank you once again, and here’s to more learning and growth!