Skip to main content

Construct segment tree from array

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

Construct segment tree

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;
        SegmentTree task = new SegmentTree(arr,n);
        task.printElement(arr, n);
        // Case A
        // front = 2, tail = 5
        task.nodeSum(2, 5);
        // Case B
        // front = 0, tail = 3
        task.nodeSum(0, 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]);
	SegmentTree task = SegmentTree(arr, n);
	task.printElement(arr, n);
	// Case A
	// front = 2, tail = 5
	task.nodeSum(2, 5);
	// Case B
	// front = 0, tail = 3
	task.nodeSum(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
// 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);
		task.printElement(arr, n);
		// Case A
		// front = 2, tail = 5
		task.nodeSum(2, 5);
		// Case B
		// front = 0, tail = 3
		task.nodeSum(0, 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);
	$task = new SegmentTree($arr, $n);
	$task->printElement($arr, $n);
	$task->nodeSum(2, 5);
	$task->nodeSum(0, 3);
}
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);
	task.printElement(arr, n);
	// Case A
	// front = 2, tail = 5
	task.nodeSum(2, 5);
	// Case B
	// front = 0, tail = 3
	task.nodeSum(0, 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)
	task = SegmentTree(arr, n)
	task.printElement(arr, n)
	#  Case A
	#  front = 2, tail = 5
	task.nodeSum(2, 5)
	#  Case B
	#  front = 0, tail = 3
	task.nodeSum(0, 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_reader :node, :size, :n
	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
	task = SegmentTree.new(arr, n)
	task.printElement(arr, n)
	#  Case A
	#  front = 2, tail = 5
	task.nodeSum(2, 5)
	#  Case B
	#  front = 0, tail = 3
	task.nodeSum(0, 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));
		task.printElement(arr, n);
		// Case A
		// front = 2, tail = 5
		task.nodeSum(2, 5);
		// Case B
		// front = 0, tail = 3
		task.nodeSum(0, 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);
	task.printElement(arr, n);
	// Case A
	// front = 2, tail = 5
	task.nodeSum(2, 5);
	// Case B
	// front = 0, tail = 3
	task.nodeSum(0, 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);
	task.printElement(arr, n);
	// Case A
	// front = 2, tail = 5
	task.nodeSum(2, 5);
	// Case B
	// front = 0, tail = 3
	task.nodeSum(0, 3);
}

Output

 2 5 1 9 4 8 7 1
 Given range (2, 5)
 Sum : 22
 Given range (0, 3)
 Sum : 17
Implementation of segment tree
Last updated on by Kalkicode




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.

New Comment