*54*

# Segment Tree in Java

**Segment Tree** is also a binary tree, but it is used to solve specific problems with better time complexity. Similar to the heap, the **segment tree in Java** is also represented with the help of an array.

## Scenario Where Segment Tree is Used

Let’s understand in which scenario a segment tree comes in handy.

Suppose we have got an array a[] = {0, 1, …, n – 1}; and it is asked to perform two tasks on this array. The tasks are:

- Compute the sum of the elements from index x to y, where 0 <= x <= y <= n – 1
- Change the value of an element of the array a[] to the new value p, i.e., one is required to do a[j] = p, where 0 <= j <= n – 1.

Let’s discuss various approaches to find the solution to the above-mentioned task.

### Native Approach:

Completion of these tasks is easy. One can run a for-loop from index x to y and can compute the cumulative sum of elements lying between index x to y. If we analyze the time complexity of finding the sum, we get O(n) time.

Also, to update the value at the j^{th }index, one can do a[j] = p, and this operation take O(1) time. So, the overall time complexity to perform both the task is O(n) + O(1) = O(n).

### Another Approach:

The other approach is to create a prefix array in advance and then complete the above-mentioned tasks. After the creation of the prefix array, the sum of elements from index x to y takes O(1) time. However, the updation at the j^{th }index will now take O(n) time. It is because the update of any index will be the prefix array, and the updation takes O(1) time. Thus, the overall time complexity turns out to be O(1) + O(n) = O(n), which is the same as the naive approach.

Since the overall time complexity remains the same in both approaches, we need to find a way to reduce its time complexity, and the way is the usage of a segment tree. The segment tree takes O(log(n)) time to compute the sum from index x to y. For updating the value at the j^{th} index, the segment tree takes O(log(n)) time. Thus, overall time complexity becomes O(log(n)) + O(log(n)) = O(2 *(log(n)), which is less than O(n).

## Representation of a Segment Tree

- The leaf nodes represent elements of the array.
- Internal nodes of the tree are generated by merging their child nodes. Since we are using an array to represent a segment tree, a node sitting at index j has the left child at 2 * j + 1 and right child at 2 * j + 2, and the parent of the node at the index j is
**⌊**(j – 1) / 2⌋.

Thus, for the array a[] = {2, 4, 7, 10, 12, 13}, the representation of segment tree as an array will be:

segArr[] = {48, 13, 35, 6, 7, 22, 13, 2, 4, k, k, 10, 12, k, k};, where k is a dummy value. The dummy values are of no use. In fact, it is the wastage of some space because of the array representation.

The segment tree will be:

The red-coloured nodes (leaf nodes) represent the elements of the array, while the orange-coloured nodes are the result of merging their child nodes.

## Size of the Array Used in Segment Tree Representation

If the size of the input array is of power 2, then there are no dummy nodes. Thus, the size of the segment tree is (2 * n – 1), where n is the size of the input array. It is because the total number of leaf nodes will be s, and internal nodes will be n – 1. Therefore, n + n – 1 = 2 * n – 1 is the total size of the array.

If the size of the input array is not of the power 2, then the size of the segment tree is 2 * y – 1, where y is the smallest power of 2 greater than n. For example, if the value of n is 9, then the smallest power of 2 greater than 9 is 16. So, y is 16.

## Pseudo Code for the Given Range Sum

After the construction of the segment tree, the challenge is to compute the sum using the segment tree. The following pseudo-code tackles the issue.

## Updating a Value in Segment Tree

The update operation in a segment tree is done recursively. Suppose the j^{th }index needs to be updated and the value is *val*. Starting from the root of the segment tree, add the value *val* to all those nodes whose range contains the given range. If the range of a given node does not contain a given index, then one should not make any changes to that node.

## Implementation of the Segment Tree

The following program shows the implementation of the segment tree.

**FileName:** SegTree.java

**Output:**

Sum of values in the given range 1 to 4 = 33 Updated sum of values in the given range = 34