Segment Tree in Java
A Segment Tree is a binary tree used for storing intervals or segments. It is allowed to query sum, minimum, maximum or other associative operations over the range of elements in the array efficiently. Each node in the segment tree represents the interval of an array. Leaves of the segment tree corresponding to the individual elements of an array. Each internal nodes is store information such as sum, minimum, and maximum about the segment that union of its children segments.
Segment trees are particularly useful in scenarios where multiple range queries and updates on the array, provide an efficient way to perform these operations with the logarithmic time complexity.
Organization of a Segment Tree
A segment tree is a binary tree where each node represents the interval or segment of the array. The root of the segment tree represents the entire array and each leaf represents the single element of an array. Internal nodes represent the union of the children intervals.
Representation of Segment Tree:
- Let us consider the array [ 1, 3, 5, 7, 9, 11 ]
Explanation of the Image:
Leaf Nodes are represent the individual elements of an array. Leaf Nodes are :
- [0, 0] represent the first element of the array i.e. 1.
- [1, 1] represent the first element of the array i.e. 3.
- [2, 2] represent the first element of the array i.e. 5.
- [3, 3] represent the first element of the array i.e. 7.
- [4, 4] represent the first element of the array i.e. 9.
- [5, 5] represent the first element of the array i.e. 11.
Internal Nodes are represent the sum of their children. Internal Nodes are:
- [0, 1] represent the sum of the elements 1 and 3.
- [0, 2] represent the sum of the elements 1, 3 and 5.
- [0, 3] represent the sum of the elements 7 and 9.
- [0, 4] represent the sum of the elements 7, 9 and 11.
- [0, 5] represent the sum of all the elements in the array.
Program for Implementation of Segment Tree
Below is the program for implementation of Segment Tree:
// Java Program to implementation of Segment Tree
class SegmentTreeNode {
// Range of indices covered by this node
int start, end;
// Sum of values in the range
int sum;
// Pointers to left and right child nodes
SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.sum = 0;
this.left = null;
this.right = null;
}
}
// Segment Tree Class
public class SegmentTree {
// Root of the segment tree
private SegmentTreeNode root;
public SegmentTree(int[] nums) {
root = buildTree(nums, 0, nums.length - 1);
}
// Build the segment tree recursively
private SegmentTreeNode buildTree(int[] nums, int start, int end) {
if (start > end) {
return null; // Empty node
}
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start == end) {
// Leaf node: store the value directly
node.sum = nums[start];
} else {
int mid = start + (end - start) / 2;
// Build left subtree
node.left = buildTree(nums, start, mid);
// Build right subtree
node.right = buildTree(nums, mid + 1, end);
// Combine values from children
node.sum = node.left.sum + node.right.sum;
}
return node;
}
// Query the range sum [i, j]
public int rangeSum(int i, int j) {
return rangeSum(root, i, j);
}
private int rangeSum(SegmentTreeNode node, int start, int end) {
if (node == null || start > node.end || end < node.start) {
// Out of range or null node
return 0;
}
if (start <= node.start && end >= node.end) {
// Fully covered by this node
return node.sum;
}
return rangeSum(node.left, start, end) + rangeSum(node.right, start, end);
}
// Update the value at index i
public void update(int i, int val) {
update(root, i, val);
}
private void update(SegmentTreeNode node, int index, int val) {
if (node.start == node.end) {
// Leaf node: update the value
node.sum = val;
} else {
int mid = node.start + (node.end - node.start) / 2;
if (index <= mid) {
// Update left subtree
update(node.left, index, val);
} else {
// Update right subtree
update(node.right, index, val);
}
// Recalculate sum
node.sum = node.left.sum + node.right.sum;
}
}
// Main function for testing
public static void main(String[] args) {
int[] nums = {1, 3, 5, 7, 9, 11};
SegmentTree segmentTree = new SegmentTree(nums);
System.out.println("Range Sum (0, 2): " + segmentTree.rangeSum(0, 2));
// Output: 9
// Update index 1 to value 10
segmentTree.update(1, 10);
System.out.println("Range Sum (0, 2): " + segmentTree.rangeSum(0, 2));
// Output: 16
// Additional tests
System.out.println("Range Sum (1, 3): " + segmentTree.rangeSum(1, 3));
// Output: 22
System.out.println("Range Sum (2, 5): " + segmentTree.rangeSum(2, 5));
// Output: 32
// Update index 4 to value 6
segmentTree.update(4, 6);
System.out.println("Range Sum (3, 5): " + segmentTree.rangeSum(3, 5));
// Output: 24
}
}
Output
Range Sum (0, 2): 9 Range Sum (0, 2): 16 Range Sum (1, 3): 22 Range Sum (2, 5): 32 Range Sum (3, 5): 24
Complexity of the Above Method
Operation | Explanation | Complexity |
|---|---|---|
Build Operation | Build operation is used to construct the segment tree from the given array. |
|
Range Query Operation | Range query operation is retrieve the aggregate information such as sum, minimum or maximum over the specified range. |
|
Update Operation | Update operation is used to modify the value of element in an array and it is update the corresponding segment tree nodes. |
|
Applications of Segment Tree:
Segment trees are the powerful data structures with the different applications in computational problems where the efficient querying and updates over the range are required. Here are the some applications of the segment tree:
- Range Sum Queries
- Range Minimum/Maximum Queries
- Range GCD Queries
- Range Update Queries
- Inversion Count in an Array
- Finding the k-th Smallest Element in a Subarray