Segment Tree Implementation in Java

A segment tree is a versatile data structure that is primarily used for answering range queries over an array, such as finding the sum, minimum, or maximum of elements in a subarray. It allows querying and updating elements efficiently.

Program Structure

The segment tree implementation consists of one main class:

• SegmentTree: Manages the construction of the tree, as well as range query and update operations.

SegmentTree Class

This class encapsulates the entire functionality of the segment tree. It contains the following components:

• Constructor: Initializes the segment tree with a given array and builds the tree.
• buildTree: Recursively builds the segment tree from the given array.
• rangeQuery: Queries the segment tree for a specific range, such as a sum, minimum, or maximum.
• update: Updates an element in the original array and reflects the change in the segment tree.

Java Code Implementation

SegmentTree Class


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

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

private void buildTree(int[] arr) {
// Initialize leaves
for (int i = 0; i < n; i++) {
tree[n + i] = arr[i];
}

// Build the tree by calculating parents
for (int i = n – 1; i > 0; i–) {
tree[i] = tree[2 * i] + tree[2 * i + 1]; // Sum operation
}
}

public void update(int index, int value) {
// Update the value at the leaf node
index += n;
tree[index] = value;

// Update the internal nodes
for (int i = index; i > 1; i /= 2) {
tree[i / 2] = tree[i] + tree[i ^ 1];
}
}

public int rangeQuery(int left, int right) {
int sum = 0;
left += n;
right += n;

while (left < right) {
if ((left & 1) == 1) {
sum += tree[left];
left++;
}
if ((right & 1) == 1) {
right–;
sum += tree[right];
}
left /= 2;
right /= 2;
}
return sum;
}
}

Explanation

Here is a detailed explanation of the key components in the SegmentTree class:

1. Constructor

The constructor accepts an integer array and initializes the segment tree. The tree is represented by an array that is twice the size of the original array. The buildTree method is called to populate the segment tree based on the input array.

2. buildTree Method

This method builds the segment tree from the input array. The leaves of the tree (the last n elements) are initialized with the array values. The internal nodes are then calculated as the sum of their respective child nodes. The operation performed (in this case, sum) can be modified depending on the use case (e.g., finding minimum or maximum).

3. update Method

This method updates a value in the original array and adjusts the segment tree accordingly. The update starts at the leaf node corresponding to the updated element and propagates the change up to the root, ensuring that all relevant internal nodes are updated.

4. rangeQuery Method

The range query method returns the sum of the elements between two indices (inclusive). It traverses the segment tree, adding the values of the relevant nodes while skipping irrelevant nodes to optimize performance. The sum operation can be replaced with other operations like minimum or maximum as needed.

Conclusion

This segment tree implementation in Java allows for efficient range queries and updates. The segment tree is particularly useful for scenarios where an array undergoes frequent updates and range queries, as it reduces the time complexity compared to naive approaches.