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