In this post, we will see about Segment Tree in java.

## Problem

Consider an Array of Integers,

int[] arr = {a1, a2, a3, a4, a5,….., an};

Given two types of queries,

(i) In the first type of query, given two integers, L & R, Output the sum of the elements in the

given range.

(ii) In the second type of query, given an Index and a value, update the value in array at the

given index to the given value.

**Input format:**

First line will contain an integer n, that is, the length of the given array.

Next line contains N space separated integers which are the elements of the array.

next line will contain the number of queries.

Next q lines will contain 2 space separated integers, if the first integer is ‘1’ then it will be a range sum query, if the first integer is ‘2’ then it will be an update query.

**INPUT :**

8

2 6 4 -3 5 -1 6 10

3

1 2 4

2 3 3

1 2 4

**OUTPUT :**

6

12

Here

**1 2 4**

1 represents range sum query, so we need to find sum of elements from index to 2 to 4.

so answer is **6** (4 + -3 + 5)

**2 3 3**

2 represents update query, so we will update index 3 with value 3 in the array, so array will become

2 6 4 3 5 -1 6 10

**1 2 4**

Again same query as before but since value at index 3 is updated, we will get result as **12** (4 + 3 + 5)

## Solution

**Approach – I:**

- For the first type of query, when the sum of the given range is asked, we run a loop from L to R and add the every every element in the range to a variable and output the variable to give the sum of the given range.
- For second type of query, we update the value at the given index in the query.

The complexity for the range query operation is**O(n)**and for update operation it is**O(1)**as we directly reach to the given index and update the value which takes constant time. - Therefore, overall worst time complexity of this approach is
**: O(n) + O(1)**

**: O(n)**

**Approach – II:**

Instead of looping in whole array every time to **find a range sum**, we can create a** prefix sum array** in **O(n)** time before we solve any query. This prefix sum array contains the sum of the array starting from 0*th* index to* i th* index in the given array. This boils down the time complexity for range sum query to **O(1)** as the sum of range **[L,R]** can be found by,

- rangesum = prefixsum[R] – prefixsum[L-1] {where L > 0}

rangesum = prefixsum[R] {where L = 0}

Now for **update query**, whenever an element in the given array is changed, the prefix sum of all the indices in range *[i, arr.length()] *is effected. Now the worst time complexity for updation becomes **O(n)**.

The worst time complexity for this approach will again be : *O(1) + O(n)* = **O(n)**

**Efficient Approach :**

For solving the range queries and updates which can be point or range, we use **Segment tree** which is basically a **full binary tree** that is for every parent there will be either 2 or no children, which is used to solve *range queries and updations efficiently *in **O(logN)**. These range queries can be of any type such as, range sum, range min, range max, range GCD, etc. It also handles the point updation and also the range update which we will see in the later part of the article.

In this article we will discuss the calculation of Range Sum Query and point updates using Segment tree in O(log n) time complexity.

**Construction of a Segment tree**:

- Each node of the segment tree contains the sum of a range {say [L,R]} and its left child contains the sum of range [L, mid] and the right child contains the sum of range

[mid + 1, R] where mid = (L+R)/2. - The root node contains the sum of range [0, n], thats is, the sum of complete array.
- As we keep on dividing range of parent node into two halves onto its child nodes, eventually we will not be able to create more child nodes once the range of a node contains only one element, that is, with the range [i, i]. Therefore, the nodes containing the sum of a single element of array, will be the leaf nodes as its range can not be divided.
- Now all the array elements will be present at the leaf nodes and number of leaf nodes in the tree will be equal to length of the array.

**Now how do we store the tree?**

We will store the tree in an array where the index of the left child of any parent node at* i th* index will be stored at index **2*i+1** and the index of right node will be stored at index **2*i+2**.

All the leaf nodes will contain the elements of given array and the parents of these nodes will contain the sum of its left child and right child.

**What will be the size of the array?**

To answer this question we first need to know, how many nodes will be there in the complete tree.

Let us consider an array with length equal to perfect power of two to understand it more clearly.

int[] arr = {2, 6, 4, -3, 5, -1, 6, 10}

As at every next level, every node at current level is splitting into two nodes, hence the nodes at next level will be twice the nodes at current level.

*0th level will contain 2^0 that is, 1 node which is root node.*

*1st level will contain*

**2^1 nodes**.*2nd level will contain*

**2^2 nodes**.*3rd level will contain*

**2^3 nodes**.*.*

*.*

*.*

*last level will contain*

**2^height**nodes.Therefore, Total number of nodes = 2^0 + 2^1 + 2^2 + …. + 2^height

= **2^(height+1) – 1** { sum of a G.P.}

We know,

*Height of a tree = log(n) to the base 2.*

where, n = size of the given array.

Therefore, the **total nodes = 2^((log n) +1) – 1.**

As we store every node of the tree in an array, therefore,

the size of the segment array will be 2^((log n) +1) – 1.

int[] segArr = new int[2^((log n) +1) – 1];

**Construction :**

**Construction :**

- We start from root node going down deep in recursion and we set the values in postorder i.e after we set the values of its children.
- For any node we call for its two children left and right with incrementing the pointer for segment array to 2*idx+1 and 2*idx+2 respectively, also we reduce the segment length for each child to half the range of its parent.
- Whenever we encounter a leaf node which we get know when we have left limit = right limit, we straightaway put the value present at left/right in given array (since they both are equal for leaf we can use either of them) at the current index in the segment array. This would be our base case and we would return the value of this leaf node after we set it.
- In case of an inner node, its value will be calculated in postorder by summing up the values of both of its child.

**Range Sum Query :**

**Range Sum Query :**

Whenever we are given a query for finding out the sum of a given range (say [query_left, query_right]).

We keep these three points in mind:

(i) if the query range lies completely outside the segment of the current node we are currently present at, we return a value such that it does not contribute anything into our final answer because answer for the asked range lies in some other node(s).

(ii) if the query range lies completely inside the range of the current segment then we return the complete value of this segment because this segment will contribute everything to the asked range query.

(iii) if there is any overlap in the segment of the current node and the range of the query, we call for both of its children, as the current segment will contribute to the final answer but not completely.

**Updation**:

**Updation**

In updation we will be required to update the value at an index in the given array.

We start from the root node searching for the leaf node that contains the value of the asked index. Then in post order we correct the values of all those nodes which contains the updated index in their segment range.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
package org.arpit.java2blog; import java.util.Scanner; public class SegmentTree { static int[] segArr; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; // array on which operations / queries will be performed. for (int i = 0; i 0) { int check = scn.nextInt(); if (check == 1) { int ql = scn.nextInt(); int qr = scn.nextInt(); System.out.println(getQuery(0, 0, arr.length - 1, ql, qr, arr)); } else { int idx = scn.nextInt(); int value = scn.nextInt(); update(value, idx, 0, 0, arr.length - 1, arr); } } } public static int construct(int saIdx, int left, int right, int[] arr) { /* * if the segment is of length one, then we know it will be * a left node and hence it will contain an element of the given array */ if (left == right) { /* * element at the current index of segArr will be the element * present at index left or right in given array, * as left is equal to right so we can take either of them */ return segArr[saIdx] = arr[left]; } /* * current segment of parent node is divided into two halves, * if the segment for parent is [left, right], then * segment for left child will be [left, mid] and * segment for right child will be [mid+1, right]. */ int mid = (left + right) / 2; int leftChild = construct(2 * saIdx + 1, left, mid, arr); int rightChild = construct(2 * saIdx + 2, mid + 1, right, arr); /* * result of the current node will be calculated * in the post order after calculating * the result for its children */ segArr[saIdx] = leftChild + rightChild; return segArr[saIdx]; } // saIdx - pointer for the segment array. // left - left limit of the current segment. // right - right limit of the current segment. // ql - left limit of the given query segment. // qr - right limit of the given query segment. public static int getQuery(int saIdx, int left, int right, int ql, int qr, int[] arr) { /* * if the range of the query lies completely outside the range of * the current segment, we return a value which contributes nothing * to the final answer,that 0 in the case when sum is to be calculated for given range. */ if (left > qr || right = ql && right <= qr) { return segArr[saIdx]; } else { /* * if there is an overlap in the segments of the query and the node, * then we recur for both of its children, as there will be a contribution * in result from both of the sides. */ int mid = (left + right) / 2; int leftResult = getQuery(2 * saIdx + 1, left, mid, ql, qr, arr); int rightResult = getQuery(2 * saIdx + 2, mid + 1, right, ql, qr, arr); return leftResult + rightResult; } } public static void update(int value, int idx, int saIdx, int left, int right, int[] arr) { /* * if the index lies outside the range of the current segment * then there is no need for an update/call at that index, * so simply return. */ if (idx right) { return; } /* * if we found the index to be updated, we update the given array * as well as the segment array that is the node which has the * segment equal to given index. */ if (idx == left && idx == right) { arr[left] = value; segArr[saIdx] = value; return; } /* * now in post order we need to update all the nodes * which contains the given index in their segment */ else { int mid = (left + right) / 2; update(value, idx, 2 * saIdx + 1, left, mid, arr); update(value, idx, 2 * saIdx + 2, mid + 1, right, arr); segArr[saIdx] = segArr[2 * saIdx + 1] + segArr[2 * saIdx + 2]; } } } |

When you run above program, you will get below output:

2 6 4 -3 5 -1 6 10

3

1 2 4

2 3 3

1 2 4

Output:

612

That’s all about Segment tree in java