Construct segment tree from array

Segment tree leaf node contains actual array element and its top roots are indicate child sum values.

Here given code implementation process.

``````// C program for
// Construct segment tree from array
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// Display array elements
void printElement(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("  %d", arr[i]);
}
}
// Returns the sum of given range element
int findSum(int *node, int first, int last, int front, int tail, int position)
{
if (front <= first && tail >= last)
{
// Return range element
return node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
int mid = first + (last - first) / 2;
//  visiting the left and right subtree
return findSum(node, first, mid, front, tail, (position *2) + 1) + findSum(node, mid + 1, last, front, tail, (position *2) + 2);
}
// Handles the request of finding sum of given range element
void nodeSum(int *node, int n, int front, int tail)
{
if (front < 0 || tail > n - 1 || front > tail)
{
// Invalid range
return;
}
else
{
int result = findSum(node, 0, n - 1, front, tail, 0);
printf("\n Given range (%d, %d)", front, tail);
printf("\n Sum  : %d", result);
}
}
// Assign tree node value
int constructTree(int arr[], int front, int tail, int *node, int position)
{
if (front == tail)
{
// When front and tail are similar, then set new position value
node[position] = arr[front];
return node[position];
}
// Find middle node
int mid = front + (tail - front) / 2;
//  visiting the left and right subtree and set new position value using recursion
node[position] = constructTree(arr, front, mid, node, (position *2) + 1) + constructTree(arr, mid + 1, tail, node, (position *2) + 2);
return node[position];
}
// This function are allocating the memory of segment tree
// And return segment tree
int *makeTree(int arr[], int n)
{
// Calculate height of tree
int x = (int)(ceil(log2(n)));
// Get the size of tree
int max_size = 2 *(int) pow(2, x) - 1;
// Allocate tree node memory
int *node = (int *) malloc(sizeof(int) *max_size);
// Assign the element values
constructTree(arr, 0, n - 1, node, 0);
return node;
}
int main(int argc, char
const *argv[])
{
int arr[] = {
2 , 5 , 1 , 9 , 4 , 8 , 7 , 1
};
int n = sizeof(arr) / sizeof(arr[0]);
int *result = makeTree(arr, n);
printElement(arr, n);
// Case A
// front = 2, tail = 5
nodeSum(result, n, 2, 5);
// Case B
// front = 0, tail = 3
nodeSum(result, n, 0, 3);
return 0;
}``````

Output

``````  2  5  1  9  4  8  7  1
Given range (2, 5)
Sum  : 22
Given range (0, 3)
Sum  : 17``````
``````// Java Program
// Construct segment tree from array
public class SegmentTree
{
public int[] node;
public int size;
public int n;
public SegmentTree(int arr[], int n)
{
this.n = n;
this.size = treeSize();
// Allocate memory of node
this.node = new int[this.size];
this.constructTree(arr, 0, n - 1, 0);
}
public int treeSize()
{
// Calculate tree height
int height = (int)(Math.ceil(Math.log(this.n) / Math.log(2)));

// returns the size of tree
return 2 * (int) Math.pow(2, height) - 1;
}
// Assign tree node value
public int constructTree(int[] arr, int front, int tail, int position)
{
if (front == tail)
{
// When front and tail are similar, then set new position value
this.node[position] = arr[front];
return arr[front];
}
// Find middle node
int mid = front + (tail - front) / 2;
//  visiting the left and right subtree and set new position value using recursion
this.node[position] = constructTree(arr, front, mid, (position * 2) + 1) +
constructTree(arr, mid + 1, tail, (position * 2) + 2);
return this.node[position];
}
// Returns the sum of given range element
public int findSum(int first, int last, int front, int tail, int position)
{
if (front <= first && tail >= last)
{
// Return range element
return this.node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
int mid = first + (last - first) / 2;
//  visiting the left and right subtree
return findSum(first, mid, front, tail, (position * 2) + 1) +
findSum(mid + 1, last, front, tail, (position * 2) + 2);
}
// Handles the request of finding sum of given range element
public void nodeSum(int front, int tail)
{
if (front < 0 || tail > this.n - 1 || front > tail)
{
// Invalid range
return;
}
else
{
int result = findSum( 0, this.n - 1, front, tail, 0);
System.out.print("\n Given range (" + front + ", " + tail + ")");
System.out.print("\n Sum : " + result);
}
}
// Display array elements
public void printElement(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public static void main(String[] args)
{

int arr[] =
{
2 , 5 , 1 , 9 , 4 , 8 , 7 , 1
};
int n = arr.length;
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
}
}``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````// Include header file
#include <iostream>

#include <math.h>

using namespace std;
// C++ Program
// Construct segment tree from array
class SegmentTree
{
public: int *node;
int size;
int n;
SegmentTree(int arr[], int n)
{
this->n = n;
this->size = treeSize();
// Allocate memory of node
this->node = new int[this->size];
this->constructTree(arr, 0, n - 1, 0);
}
int treeSize()
{
// Calculate tree height
int height = (int)(ceil(log(this->n) / log(2)));
// returns the size of tree
return (2 * (int) pow(2, height)) - 1;
}
// Assign tree node value
int constructTree(int arr[], int front, int tail, int position)
{
if (front == tail)
{
// When front and tail are similar, then set new position value
this->node[position] = arr[front];
return arr[front];
}
// Find middle node
int mid = front + (tail - front) / 2;
//  visiting the left and right subtree and set new position value using recursion
this->node[position] = this->constructTree(arr, front, mid, (position *2) + 1) +
this->constructTree(arr, mid + 1, tail, (position *2) + 2);
return this->node[position];
}
// Returns the sum of given range element
int findSum(int first, int last, int front, int tail, int position)
{
if (front <= first && tail >= last)
{
// Return range element
return this->node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
int mid = first + (last - first) / 2;
//  visiting the left and right subtree
return this->findSum(first, mid, front, tail, (position *2) + 1) +
this->findSum(mid + 1, last, front, tail, (position *2) + 2);
}
// Handles the request of finding sum of given range element
void nodeSum(int front, int tail)
{
if (front < 0 || tail > this->n - 1 || front > tail)
// Invalid range
{
return;
}
else
{
int result = this->findSum(0, this->n - 1, front, tail, 0);
cout << "\n Given range (" << front << ", " << tail << ")";
cout << "\n Sum : " << result;
}
}
// Display array elements
void printElement(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
};
int main()
{
int arr[] = {
2 , 5 , 1 , 9 , 4 , 8 , 7 , 1
};
int n = sizeof(arr) / sizeof(arr[0]);
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
return 0;
}``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````// Include namespace system
using System;
using System.Collections.Generic;

// C# Program
// Construct segment tree from array

public class SegmentTree
{
public int[] node;
public int size;
public int n;
public SegmentTree(int[] arr, int n)
{
this.n = n;
this.size = treeSize();
// Allocate memory of node
this.node = new int[this.size];
this.constructTree(arr, 0, n - 1, 0);
}
public int treeSize()
{
// Calculate tree height
int height = (int)(Math.Ceiling(Math.Log(this.n) / Math.Log(2)));
// returns the size of tree
return 2 * (int) Math.Pow(2, height) - 1;
}
// Assign tree node value
public int constructTree(int[] arr, int front, int tail, int position)
{
if (front == tail)
{
// When front and tail are similar, then set new position value
this.node[position] = arr[front];
return arr[front];
}
// Find middle node
int mid = front + (tail - front) / 2;
//  visiting the left and right subtree and set new position value using recursion
this.node[position] = constructTree(arr, front, mid, (position * 2) + 1) +
constructTree(arr, mid + 1, tail, (position * 2) + 2);
return this.node[position];
}
// Returns the sum of given range element
public int findSum(int first, int last, int front, int tail, int position)
{
if (front <= first && tail >= last)
{
// Return range element
return this.node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
int mid = first + (last - first) / 2;
//  visiting the left and right subtree
return findSum(first, mid, front, tail, (position * 2) + 1) +
findSum(mid + 1, last, front, tail, (position * 2) + 2);
}
// Handles the request of finding sum of given range element
public void nodeSum(int front, int tail)
{
if (front < 0 || tail > this.n - 1 || front > tail)
{	// Invalid range
return;
}
else
{
int result = findSum(0, this.n - 1, front, tail, 0);
Console.Write("\n Given range (" + front + ", " + tail + ")");
Console.Write("\n Sum : " + result);
}
}
// Display array elements
public void printElement(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public static void Main(String[] args)
{
int[] arr = {
2 , 5 , 1 , 9 , 4 , 8 , 7 , 1
};
int n = arr.Length;
SegmentTree task = new SegmentTree(arr, n);
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
}
}``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````<?php
// Php Program
// Construct segment tree from array
class SegmentTree
{
public \$node;
public \$size;
public \$n;

function __construct( & \$arr, \$n)
{
\$this->n = \$n;
\$this->size = \$this->treeSize();
// Allocate memory of node
\$this->node = array_fill(0, \$this->size, 0);
\$this->constructTree(\$arr, 0, \$n - 1, 0);
}
public	function treeSize()
{
// Calculate tree height
\$height = (int)(ceil(intval(log(\$this->n) / log(2))));
// returns the size of tree
return 2 * (int) pow(2, \$height) - 1;
}
// Assign tree node value
public	function constructTree( & \$arr, \$front, \$tail, \$position)
{
if (\$front == \$tail)
{
// When front and tail are similar, then set new position value
\$this->node[\$position] = \$arr[\$front];
return \$arr[\$front];
}
// Find middle node
\$mid = \$front + intval((\$tail - \$front) / 2);
//  visiting the left and right subtree and set new position value using recursion
\$this->node[\$position] = \$this->constructTree(\$arr, \$front, \$mid, (\$position * 2) + 1) +
\$this->constructTree(\$arr, \$mid + 1, \$tail, (\$position * 2) + 2);
return \$this->node[\$position];
}
// Returns the sum of given range element
public	function findSum(\$first, \$last, \$front, \$tail, \$position)
{
if (\$front <= \$first && \$tail >= \$last)
{
// Return range element
return \$this->node[\$position];
}
else if (\$last < \$front || \$first > \$tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
\$mid = \$first + intval((\$last - \$first) / 2);
//  visiting the left and right subtree
return \$this->findSum(\$first, \$mid, \$front, \$tail, (\$position * 2) + 1) +
\$this->findSum(\$mid + 1, \$last, \$front, \$tail, (\$position * 2) + 2);
}
// Handles the request of finding sum of given range element
public	function nodeSum(\$front, \$tail)
{
if (\$front < 0 || \$tail > \$this->n - 1 || \$front > \$tail)
// Invalid range
{
return;
}
else
{
\$result = \$this->findSum(0, \$this->n - 1, \$front, \$tail, 0);
echo "\n Given range (". \$front .", ". \$tail .")";
echo "\n Sum : ". \$result;
}
}
// Display array elements
public	function printElement( & \$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo " ". \$arr[\$i];
}
}
}

function main()
{
\$arr = array(2, 5, 1, 9, 4, 8, 7, 1);
\$n = count(\$arr);
}
main();``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````// Node Js Program
// Construct segment tree from array
class SegmentTree
{
treeSize()
{
// Calculate tree height
var height = parseInt((Math.ceil(parseInt(Math.log(this.n) / Math.log(2)))));
// returns the size of tree
return 2 * parseInt(Math.pow(2, height)) - 1;
}
constructor(arr, n)
{
this.n = n;
this.size = this.treeSize();
// Allocate memory of node
this.node = Array(this.size).fill(0);
this.constructTree(arr, 0, n - 1, 0);
}
// Assign tree node value
constructTree(arr, front, tail, position)
{
if (front == tail)
{
// When front and tail are similar, then set new position value
this.node[position] = arr[front];
return arr[front];
}
// Find middle node
var mid = front + parseInt((tail - front) / 2);
//  visiting the left and right subtree and set new position value using recursion
this.node[position] = this.constructTree(arr, front, mid, (position * 2) + 1) +
this.constructTree(arr, mid + 1, tail, (position * 2) + 2);
return this.node[position];
}
// Returns the sum of given range element
findSum(first, last, front, tail, position)
{
if (front <= first && tail >= last)
{
// Return range element
return this.node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
var mid = first + parseInt((last - first) / 2);
//  visiting the left and right subtree
return this.findSum(first, mid, front, tail, (position * 2) + 1) +
this.findSum(mid + 1, last, front, tail, (position * 2) + 2);
}
// Handles the request of finding sum of given range element
nodeSum(front, tail)
{
if (front < 0 || tail > this.n - 1 || front > tail)
// Invalid range
{
return;
}
else
{
var result = this.findSum(0, this.n - 1, front, tail, 0);
process.stdout.write("\n Given range (" + front + ", " + tail + ")");
process.stdout.write("\n Sum : " + result);
}
}
// Display array elements
printElement(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
}

function main()
{
var arr = [2, 5, 1, 9, 4, 8, 7, 1];
var n = arr.length;
var task = new SegmentTree(arr, n);
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
}
main();``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````import math
#  Python 3 Program
#  Construct segment tree from array
class SegmentTree :

def treeSize(self) :
#  Calculate tree height
height = int((math.ceil(int(math.log(self.n) / math.log(2)))))
#  returns the size of tree
return 2 * int(math.pow(2, height)) - 1

def __init__(self, arr, n) :
self.n = n
self.size = self.treeSize()
#  Allocate memory of node
self.node = [0] * (self.size)
self.constructTree(arr, 0, n - 1, 0)

#  Assign tree node value
def constructTree(self, arr, front, tail, position) :
if (front == tail) :
#  When front and tail are similar, then set new position value
self.node[position] = arr[front]
return arr[front]

#  Find middle node
mid = front + int((tail - front) / 2)
#   visiting the left and right subtree and set new position value using recursion
self.node[position] = self.constructTree(arr, front, mid, (position * 2) + 1) + \
self.constructTree(arr, mid + 1, tail, (position * 2) + 2)
return self.node[position]

#  Returns the sum of given range element
def findSum(self, first, last, front, tail, position) :
if (front <= first and tail >= last) :
#  Return range element
return self.node[position]

elif(last < front or first > tail) :
#  When element is outside the range
return 0

#  Find the middle position of given range
mid = first + int((last - first) / 2)
#   visiting the left and right subtree
return self.findSum(first, mid, front, tail, (position * 2) + 1) + \
self.findSum(mid + 1, last, front, tail, (position * 2) + 2)

#  Handles the request of finding sum of given range element
def nodeSum(self, front, tail) :
if (front < 0 or tail > self.n - 1 or front > tail):
#  Invalid range
return
else :
result = self.findSum(0, self.n - 1, front, tail, 0)
print("\n Given range (", front ,", ", tail ,")", end = "")
print("\n Sum : ", result, end = "")

#  Display list elements
def printElement(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

def main() :
arr = [2, 5, 1, 9, 4, 8, 7, 1]
n = len(arr)
#  Case A
#  front = 2, tail = 5
#  Case B
#  front = 0, tail = 3

if __name__ == "__main__": main()``````

Output

``````  2  5  1  9  4  8  7  1
Given range ( 2 ,  5 )
Sum :  22
Given range ( 0 ,  3 )
Sum :  17``````
``````#  Ruby Program
#  Construct segment tree from array
class SegmentTree
# Define the accessor and reader of class SegmentTree
attr_accessor :node, :size, :n

def treeSize()
#  Calculate tree height
height = (((Math.log(self.n) / Math.log(2))).ceil()).to_i
#  returns the size of tree
return 2 * (2**height).to_i - 1
end
def initialize(arr, n)
self.n = n
self.size = self.treeSize()
#  Allocate memory of node
self.node = Array.new(self.size) {0}
self.constructTree(arr, 0, n - 1, 0)
end

#  Assign tree node value
def constructTree(arr, front, tail, position)
if (front == tail)
#  When front and tail are similar, then set new position value
self.node[position] = arr[front]
return arr[front]
end

#  Find middle node
mid = front + (tail - front) / 2
#   visiting the left and right subtree and set new position value using recursion
self.node[position] = self.constructTree(arr, front, mid, (position * 2) + 1) +
self.constructTree(arr, mid + 1, tail, (position * 2) + 2)
return self.node[position]
end

#  Returns the sum of given range element
def findSum(first, last, front, tail, position)
if (front <= first && tail >= last)
#  Return range element
return self.node[position]
elsif(last < front || first > tail)
#  When element is outside the range
return 0
end

#  Find the middle position of given range
mid = first + (last - first) / 2
#   visiting the left and right subtree
return self.findSum(first, mid, front, tail, (position * 2) + 1) +
self.findSum(mid + 1, last, front, tail, (position * 2) + 2)
end

#  Handles the request of finding sum of given range element
def nodeSum(front, tail)
if (front < 0 || tail > self.n - 1 || front > tail)
#  Invalid range

return
else
result = self.findSum(0, self.n - 1, front, tail, 0)
print("\n Given range (", front ,", ", tail ,")")
print("\n Sum : ", result)
end

end

#  Display array elements
def printElement(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

end

end

def main()
arr = [2, 5, 1, 9, 4, 8, 7, 1]
n = arr.length
#  Case A
#  front = 2, tail = 5
#  Case B
#  front = 0, tail = 3
end

main()``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````// Scala Program
// Construct segment tree from array
class SegmentTree(var node: Array[Int] , var size: Int , var n: Int)
{
def this(n: Int, arr: Array[Int], size: Int)
{
this(Array.fill[Int](size)(0), size, n);
this.constructTree(arr, 0, n - 1, 0);
}
// Assign tree node value
def constructTree(arr: Array[Int], front: Int, tail: Int, position: Int): Int = {
if (front == tail)
{
// When front and tail are similar, then set new position value
this.node(position) = arr(front);
return arr(front);
}
// Find middle node
var mid: Int = front + ((tail - front) / 2).toInt;
//  visiting the left and right subtree and set new position value using recursion
this.node(position) = this.constructTree(arr, front, mid, (position * 2) + 1) +
this.constructTree(arr, mid + 1, tail, (position * 2) + 2);
return this.node(position);
}
// Returns the sum of given range element
def findSum(first: Int, last: Int, front: Int, tail: Int, position: Int): Int = {
if (front <= first && tail >= last)
{
// Return range element
return this.node(position);
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
var mid: Int = first + ((last - first) / 2).toInt;
//  visiting the left and right subtree
return this.findSum(first, mid, front, tail, (position * 2) + 1) +
this.findSum(mid + 1, last, front, tail, (position * 2) + 2);
}
// Handles the request of finding sum of given range element
def nodeSum(front: Int, tail: Int): Unit = {
if (front < 0 || tail > this.n - 1 || front > tail)
// Invalid range
{
return;
}
else
{
var result: Int = this.findSum(0, this.n - 1, front, tail, 0);
print("\n Given range (" + front + ", " + tail + ")");
print("\n Sum : " + result);
}
}
// Display array elements
def printElement(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
}
object Main
{
def treeSize(n: Int): Int = {
// Calculate tree height
var height: Int = ((Math.ceil((Math.log(n) / Math.log(2)).toInt))).toInt;
// returns the size of tree
return 2 * (Math.pow(2, height)).toInt - 1;
}
def main(args: Array[String]): Unit = {
var arr: Array[Int] = Array(2, 5, 1, 9, 4, 8, 7, 1);
var n: Int = arr.length;
var task: SegmentTree = new SegmentTree(n, arr, treeSize(n));
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
}
}``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````
``````import Foundation
// Swift 4 Program
// Construct segment tree from array
class SegmentTree
{
var node: [Int];
var size: Int;
var n: Int;

init(_ arr: [Int], _ n: Int)
{
self.n = n;
// Calculate tree height
let height: Int = Int((ceil(log(Float(self.n)) / log(Float(2)))));
// returns the size of tree
self.size = 2 * Int(pow(Double(2), Double(height))) - 1;
// Allocate memory of node
self.node = Array(repeating: 0, count: self.size);
let _ = self.constructTree(arr, 0, n - 1, 0);
}

// Assign tree node value
func constructTree(_ arr: [Int], _ front: Int, _ tail: Int, _ position: Int)->Int
{
if (front == tail)
{
// When front and tail are similar, then set new position value
self.node[position] = arr[front];
return arr[front];
}
// Find middle node
let mid: Int = front + (tail - front) / 2;
//  visiting the left and right subtree and set new position value using recursion
self.node[position] = self.constructTree(arr, front, mid, (position * 2) + 1)
+ self.constructTree(arr, mid + 1, tail, (position * 2) + 2);
return self.node[position];
}
// Returns the sum of given range element
func findSum(_ first: Int, _ last: Int, _ front: Int, _ tail: Int, _ position: Int)->Int
{
if (front <= first && tail >= last)
{
// Return range element
return self.node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
let mid: Int = first + (last - first) / 2;
//  visiting the left and right subtree
return self.findSum(first, mid, front, tail, (position * 2) + 1)
+ self.findSum(mid + 1, last, front, tail, (position * 2) + 2);
}
// Handles the request of finding sum of given range element
func nodeSum(_ front: Int, _ tail: Int)
{
if (front < 0 || tail > self.n - 1 || front > tail)
// Invalid range
{
return;
}
else
{
let result: Int = self.findSum(0, self.n - 1, front, tail, 0);
print("\n Given range (", front ,", ", tail ,")", terminator: "");
print("\n Sum : ", result, terminator: "");
}
}
// Display array elements
func printElement(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
}
func main()
{
let arr: [Int] = [2, 5, 1, 9, 4, 8, 7, 1];
let n: Int = arr.count;
let task: SegmentTree = SegmentTree(arr, n);
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
}
main();``````

Output

``````  2  5  1  9  4  8  7  1
Given range ( 2 ,  5 )
Sum :  22
Given range ( 0 ,  3 )
Sum :  17``````
``````// Kotlin Program
// Construct segment tree from array
class SegmentTree
{
var node: Array < Int > ;
var size: Int;
var n: Int;
fun treeSize(): Int
{
// Calculate tree height
var height: Int = (Math.ceil(Math.log(this.n.toDouble()) / Math.log(2.0))).toInt();
// returns the size of tree
return 2 * (Math.pow(2.0, height.toDouble())).toInt() - 1;
}
constructor(arr: Array < Int > , n: Int)
{
this.n = n;
this.size = this.treeSize();
// Allocate memory of node
this.node = Array(this.size)
{
0
};
this.constructTree(arr, 0, n - 1, 0);
}
// Assign tree node value
fun constructTree(arr: Array <Int> , front: Int, tail: Int, position: Int): Int
{
if (front == tail)
{
// When front and tail are similar, then set new position value
this.node[position] = arr[front];
return arr[front];
}
// Find middle node
var mid: Int = front + (tail - front) / 2;
//  visiting the left and right subtree and set new position value using recursion
this.node[position] = this.constructTree(arr, front, mid, (position * 2) + 1) +
this.constructTree(arr, mid + 1, tail, (position * 2) + 2);
return this.node[position];
}
// Returns the sum of given range element
fun findSum(first: Int, last: Int, front: Int, tail: Int, position: Int): Int
{
if (front <= first && tail >= last)
{

// Return range element
return this.node[position];
}
else if (last < front || first > tail)
{
// When element is outside the range
return 0;
}
// Find the middle position of given range
var mid: Int = first + (last - first) / 2;

//  visiting the left and right subtree
return this.findSum(first, mid, front, tail, (position * 2) + 1) +
this.findSum(mid + 1, last, front, tail, (position * 2) + 2);
}
// Handles the request of finding sum of given range element
fun nodeSum(front: Int, tail: Int): Unit
{
if (front < 0 || tail > this.n - 1 || front > tail)
// Invalid range
{
return;
}
else
{
var result: Int = this.findSum(0, this.n - 1, front, tail, 0);
print("\n Given range (" + front + ", " + tail + ")");
print("\n Sum : " + result);
}
}
// Display array elements
fun printElement(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
}
fun main(args: Array <String> ): Unit
{
var arr: Array <Int> = arrayOf(2, 5, 1, 9, 4, 8, 7, 1);
var n: Int = arr.count();
var task: SegmentTree = SegmentTree(arr, n);
// Case A
// front = 2, tail = 5
// Case B
// front = 0, tail = 3
}``````

Output

`````` 2 5 1 9 4 8 7 1
Given range (2, 5)
Sum : 22
Given range (0, 3)
Sum : 17``````

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.