Segment Tree in Java
Binary trees can address a variety of issues; however, the Segment Tree is more efficient in terms of time complexity. The segment tree in Java is represented using an array.
Native Approach
It is simple to complete these activities. One may compute the cumulative sum of the elements located between index x and index y by running a for-loop from x to y. When we look at how long it will take to get the total, we obtain O(n) time.
A[j] = p can also be used to update the value at the j-th index, and this operation takes O(1) time. As a result, the total time complexity to do both tasks is O(n) + O(1) = O (n).
Other Approach
The alternative strategy is to first make a prefix array, then finish the aforementioned activities. The sum of the items from index x to index y requires O(1) time once the prefix array has been created. However, it will now take O(n) time to update the jth index. This is due to the fact that updating any index requires updating the prefix array, which takes O(1) time. It follows that the total time complexity is O(1) + O(n) = O(n), which is identical to the naïve method. Since both ways take the same amount of time overall, we must find a way to make it take less time, and the solution is to use a segment tree. The sum from index x to index y is computed in the segment tree in O(log(n)) time. The segment tree requires an O(log(n)) amount of time to update the value at the jth index. O(log(n)) + O(log(n)) = O(2 *(log(n)), which is smaller than O, is the result (n).
Segment Tree Representation
The array's elements are represented by the leaf nodes. By combining their child nodes, the internal nodes of the tree are produced. A node at index j has a left child at 2 * j + 1, a right child at 2 * j + 2, and a parent at (j - 1) / 2 since we are using an array to represent the segment tree.
Pseudo Code for Segment Tree
The difficulty is utilizing the segment tree to compute the total after the segment tree has been built.
int Sum1(node, a, b)
{
if (the range of the node is within a and b)
{
return value of the node
}
else if (the range of the node is outside of a and b)
return 0
else
return Sum1(node left child, a, b) +
getSum1(node right child, a, b)
}
Updation of Value
Recursive updating is used in segment tree operations. Assume that the value of the j-th index is val and that it has to be changed. Add the value val to all the nodes in the segment tree whose range includes the specified range, starting at the root. One should avoid making any modifications to a node if the range of that node does not contain the specified index.
Program for Segment tree using Java
SegmentTree.java
public class SegmentTree
{
int stArray[];
SegmentTree(int var[], int s1)
{
int height = (int) (Math.ceil(Math.log(s1) / Math.log(2)));
int maximum_size = 2 * (int) Math.pow(2, height) - 1;
stArray = new int[maximum_size]; constructST(var, 0, s1 - 1, 0);
}
int getMidIndex(int f1, int l1)
{
return f1 + (l1 - f1) / 2;
}
int getSumUtil(int start, int end, int i_r, int j_r, int segment_index)
{
if (i_r <= start && j_r >= end)
{
return stArray[segment_index];
}
if (end < i_r || start > j_r)
{
return 0;
}
int mid_value = getMidIndex(start, end);
return getSumUtil(start, mid_value, i_r, j_r, 2 * segment_index + 1) +
getSumUtil(mid_value + 1, end, i_r, j_r, 2 * segment_index + 2);
}
void updateValUtil(int start, int end, int j_u, int value, int segment_index)
{
if (j_u < start || j_u > end)
{
return;
}
stArray[segment_index] = stArray[segment_index] + value;
if (end != start)
{
int mid_value = getMidIndex(start, end);
updateValUtil(start, mid_value, j_u, value, 2 * segment_index + 1);
updateValUtil(mid_value + 1, end, j_u, value, 2 * segment_index + 2);
}
}
void updateVal(int N[], int s1, int j_r, int new_value)
{
if (j_r < 0 || j_r > s1 - 1)
{
System.out.println("Invalid Input");
return;
}
int different_value = new_value - N[j_r];
stArray[j_r] = new_value;
updateValUtil(0, s1 - 1, j_r, different_value, 0);
}
int getSum(int sum, int start, int end)
{
if (start < 0 || end > sum - 1 || start > end)
{
System.out.println("Invalid Input");
return -1;
}
return getSumUtil(0, sum - 1, start, end, 0);
}
int constructST(int N[], int start, int end, int segment_index)
{
if (start == end)
{
stArray [segment_index ] = N[start];
return N[start ] ;
}
int middle = getMidIndex ( start , end ) ;
stArray [ segment_index ] = constructST ( N , start, middle, segment_index * 2 + 1) +
constructST ( N , middle + 1 , end , segment_index * 2 + 2 ) ;
return stArray [ segment_index ] ;
}
public static void main(String argvs[])
{
int N[] = {22, 44, 77, 110, 2, 1};
int size_array = N.length;
SegmentTree t = new SegmentTree(N, size_array);
System.out.println ( " Sum of values within the specified range 1 to 4 = " + t . getSum ( size_array, 1, 4 ) ) ;
t. updateVal ( N , size_array , 3 , 11 ) ;
System . out . println ( " Current sum of the values in the specified range = " + t.getSum ( size_array, 1, 4 ) ) ;
}
} Output :
