Skip to main content

Segment tree update query

The segment tree is a versatile data structure often used to solve various range query problems efficiently. It's particularly useful for problems that involve finding the sum, minimum, maximum, or other aggregate values within a specific range of elements in an array. In this article, we will delve into the concept of a segment tree and its application to update queries. We will provide a detailed explanation using clear examples, step-by-step pseudocode, and an in-depth algorithmic approach. By the end, you'll have a solid understanding of segment trees and their usage for update queries.

Problem Statement

Given an array of integers, the problem is to efficiently handle two types of queries:

  1. Sum Query

    Find the sum of elements within a given range [front, tail].

  2. Update Query

    Update a specific element at a given position and adjust the segment tree accordingly.

Example Scenario

Consider the following array of integers: [2, 5, 1, 9, 4, 8, 7, 1].

Sum Query A

Finding the sum of elements in the range [2, 7].

  • Elements: 1, 9, 4, 8, 7, 1
  • Sum: 1 + 9 + 4 + 8 + 7 + 1 = 30
Sum Query B

Finding the sum of elements in the range [0, 3].

  • Elements: 2, 5, 1, 9
  • Sum: 2 + 5 + 1 + 9 = 17
Update Query

Updating the element at position 5 to the value 4.

  • Previous value at position 5: 8
  • New value at position 5: 4
Sum Query C

Finding the sum of elements in the range [2, 7] after the update.

  • Elements: 1, 9, 4, 4, 7, 1
  • Sum: 1 + 9 + 4 + 4 + 7 + 1 = 26
Sum Query D

Finding the sum of elements in the range [0, 3] after the update.

  • Elements: 2, 5, 1, 4
  • Sum: 2 + 5 + 1 + 4 = 12

Idea to Solve the Problem

The idea to solve this problem is to use a segment tree data structure. A segment tree is a binary tree where each leaf node represents an element of the array, and each internal node represents a segment of the array. The root of the tree represents the entire array. With a properly constructed segment tree, sum queries and update queries can be efficiently handled.

Pseudocode

constructTree(arr, front, tail, node, position):
    if front == tail:
        node[position] = arr[front]
        return node[position]
    mid = front + (tail - front) / 2
    node[position] = constructTree(arr, front, mid, node, 2 * position + 1) + constructTree(arr, mid + 1, tail, node, 2 * position + 2)
    return node[position]

makeTree(arr, n):
    x = ceil(log2(n))
    max_size = 2 * 2^x - 1
    node = allocate memory for max_size integers
    constructTree(arr, 0, n - 1, node, 0)
    return node

findSum(node, first, last, front, tail, position):
    if front <= first and tail >= last:
        return node[position]
    else if last < front or first > tail:
        return 0
    mid = first + (last - first) / 2
    return findSum(node, first, mid, front, tail, 2 * position + 1) + findSum(node, mid + 1, last, front, tail, 2 * position + 2)

updateElement(node, front, tail, position, difference, current):
    if position < front or position > tail:
        return
    node[current] = node[current] + difference
    if front < tail:
        mid = front + (tail - front) / 2
        updateElement(node, front, mid, position, difference, 2 * current + 1)
        updateElement(node, mid + 1, tail, position, difference, 2 * current + 2)

updateRequest(arr, n, node, position, data):
    if position < 0 or position >= n:
        return
    if arr[position] == data:
        return
    difference = data - arr[position]
    arr[position] = data
    updateElement(node, 0, n - 1, position, difference, 0)

nodeSum(node, n, front, tail):
    if front < 0 or tail > n - 1 or front > tail:
        return
    result = findSum(node, 0, n - 1, front, tail, 0)
    print("Given range ({}, {})".format(front, tail))
    print("Sum: {}".format(result))

# Main program
arr = [2, 5, 1, 9, 4, 8, 7, 1]
n = length of arr
node = makeTree(arr, n)
printElement(arr, n)
nodeSum(node, n, 2, 7)
nodeSum(node, n, 0, 3)
data = 4
position = 5
updateRequest(arr, n, node, position, data)
nodeSum(node, n, 2, 7)
nodeSum(node, n, 0, 3)

Algorithm Explanation

  1. The constructTree function constructs the segment tree by recursively dividing the array segments until reaching individual elements.

  2. The makeTree function allocates memory and constructs the segment tree.

  3. The findSum function is responsible for finding the sum of elements within a given range using recursion.

  4. The updateElement function handles element updates in the segment tree while maintaining the integrity of the tree structure.

  5. The updateRequest function updates an element in the original array and propagates the change to the segment tree.

  6. The nodeSum function handles sum queries by calling the findSum function and printing the result.

Code Solution

// C program for
// Segment tree update query
#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);
	}
}
// Perform update operation
void updateElement(int *node, int front, int tail, 
                   int position, int difference, int current)
{
	if (position < front || position > tail)
	{
		// When position is outside the range
		return;
	}
	// Update new value
	node[current] = node[current] + difference;
	if (front < tail)
	{
		// Find middle node
		int mid = front + (tail - front) / 2;
		// Visit left subtree
		updateElement(node, front, mid, position, difference, 2 *current + 1);
		// Visit right subtree
		updateElement(node, mid + 1, tail, position, difference, 2 *current + 2);
	}
}
// Handles the request to update new element at given position
void updateRequest(int arr[], int n, int *node, int position, int data)
{
	if (position < 0 || position >= n)
	{
		printf("\n Position are not valid \n");
	}
	else
	{
		// Display given data and position
		printf("\n\n Update %d at position %d \n", data, position);
		if (arr[position] == data)
		{
			// When update value is similar
			return;
		}
		else
		{
			// Get difference
			int difference = data - arr[position];
			// Set new value          
			arr[position] = data;
			// Perform tree update
			updateElement(node, 0, n - 1, position, difference, 0);
		}
	}
}
// 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 *node = makeTree(arr, n);
	printElement(arr, n);
	// Sum query A
	// front = 2, tail = 7
	nodeSum(node, n, 2, 7);
	// Sum query B
	// front = 0, tail = 3
	nodeSum(node, n, 0, 3);
	// Update info
	int data = 4;
	int position = 5;
	// Perform update operation 
	// Test
	updateRequest(arr, n, node, position, data);
	// Sum query C
	// front = 2, tail = 7
	nodeSum(node, n, 2, 7);
	// Sum query D
	// front = 0, tail = 3
	nodeSum(node, n, 0, 3);
	return 0;
}

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum  : 26
 Given range (0, 3)
 Sum  : 17
// Java Program 
// Segment tree update query
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);
        }
    }
    // Perform update operation
	public void updateElement(int front, int tail, 
							int position, int difference, int current)
	{
		if (position < front || position > tail)
		{
			// When position is outside the range
			return;
		}
		// Update new value
		this.node[current] = this.node[current] + difference;

		if (front < tail)
		{
			// Find middle node
			int mid = front + (tail - front) / 2;
			// Visit left subtree
			updateElement( front, mid, position, difference, 2 * current + 1);
			// Visit right subtree
			updateElement( mid + 1, tail, position, difference, 2 * current + 2);
		}
	}
	// Handles the request to update new element at given position
	public void updateRequest(int[] arr, int position, int data)
	{
		if (position < 0 || position >= this.n)
		{
			System.out.print("\n Position are not valid \n");
		}
		else
		{
			// Display given data and position
			System.out.print("\n\n Update " + data + " at position " + position + " \n");
			if (arr[position] == data)
			{
				// When update value is similar
				return;
			}
			else
			{
				// Get difference
				int difference = data - arr[position];
				// Set new value          
				arr[position] = data;
				// Perform tree update
				updateElement( 0, this.n - 1, position, difference, 0);
			}
		}
	}


    // 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);
		// Sum query A
		// front = 2, tail = 7
		task.nodeSum(2, 7);
		// Sum query B
		// front = 0, tail = 3
		task.nodeSum(0, 3);
		// Update info
		int data = 4;
		int position = 5;
		// Perform update operation 
		// Test
		task.updateRequest(arr, position, data);
		// Sum query C
		// front = 2, tail = 7
		task.nodeSum(2, 7);
		// Sum query D
		// front = 0, tail = 3
		task.nodeSum(0, 3);
    }
}

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
// Include header file
#include <iostream>
#include <math.h>

using namespace std;
// C++ Program
// Segment tree update query
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;
		}
	}
	// Perform update operation
	void updateElement(int front, int tail, int position, int difference, int current)
	{
		// When position is outside the range
		if (position < front || position > tail)
		{
			return;
		}
		// Update new value
		this->node[current] = this->node[current] + difference;
		if (front < tail)
		{
			// Find middle node
			int mid = front + (tail - front) / 2;
			// Visit left subtree
			this->updateElement(front, mid, position, difference, 2 *current + 1);
			// Visit right subtree
			this->updateElement(mid + 1, tail, position, difference, 2 *current + 2);
		}
	}
	// Handles the request to update new element at given position
	void updateRequest(int arr[], int position, int data)
	{
		if (position < 0 || position >= this->n)
		{
			cout << "\n Position are not valid \n";
		}
		else
		{
			cout << "\n\n Update " << data << " at position " << position << " \n";
			if (arr[position] == data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				int difference = data - arr[position];
				// Set new value
				arr[position] = data;
				// Perform tree update
				this->updateElement(0, this->n - 1, position, difference, 0);
			}
		}
	}
	// 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);
	// Sum query A
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query B
	// front = 0, tail = 3
	task.nodeSum(0, 3);
	// Update info
	int data = 4;
	int position = 5;
	// Perform update operation
	// Test
	task.updateRequest(arr, position, data);
	// Sum query C
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query D
	// front = 0, tail = 3
	task.nodeSum(0, 3);
	return 0;
}

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
// Include namespace system
using System;
using System.Collections.Generic;
// C# Program
// Segment tree update query
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);
		}
	}
	// Perform update operation
	public void updateElement(int front, int tail, int position, 
                              int difference, int current)
	{
		// When position is outside the range
		if (position < front || position > tail)
		{
			return;
		}
		// Update new value
		this.node[current] = this.node[current] + difference;
		if (front < tail)
		{
			// Find middle node
			int mid = front + (tail - front) / 2;
			// Visit left subtree
			updateElement(front, mid, position, difference, 2 * current + 1);
			// Visit right subtree
			updateElement(mid + 1, tail, position, difference, 2 * current + 2);
		}
	}
	// Handles the request to update new element at given position
	public void updateRequest(int[] arr, int position, int data)
	{
		if (position < 0 || position >= this.n)
		{
			Console.Write("\n Position are not valid \n");
		}
		else
		{
			// Display given data and position
			Console.Write("\n\n Update " + data + " at position " + position + " \n");
			if (arr[position] == data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				int difference = data - arr[position];
				// Set new value
				arr[position] = data;
				// Perform tree update
				updateElement(0, this.n - 1, position, difference, 0);
			}
		}
	}
	// 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);
		// Sum query A
		// front = 2, tail = 7
		task.nodeSum(2, 7);
		// Sum query B
		// front = 0, tail = 3
		task.nodeSum(0, 3);
		// Update info
		int data = 4;
		int position = 5;
		// Perform update operation
		// Test
		task.updateRequest(arr, position, data);
		// Sum query C
		// front = 2, tail = 7
		task.nodeSum(2, 7);
		// Sum query D
		// front = 0, tail = 3
		task.nodeSum(0, 3);
	}
}

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
<?php
// Php Program
// Segment tree update query
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(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 + (int)(($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 + (int)(($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;
		}
	}
	// Perform update operation
	public	function updateElement($front, $tail, $position, $difference, $current)
	{
		// When position is outside the range
		if ($position < $front || $position > $tail)
		{
			return;
		}
		// Update new value
		$this->node[$current] = $this->node[$current] + $difference;
		if ($front < $tail)
		{
			// Find middle node
			$mid = $front + (int)(($tail - $front) / 2);
			// Visit left subtree
			$this->updateElement($front, $mid, $position, $difference, 2 * $current + 1);
			// Visit right subtree
			$this->updateElement($mid + 1, $tail, $position, $difference, 2 * $current + 2);
		}
	}
	// Handles the request to update new element at given position
	public	function updateRequest( & $arr, $position, $data)
	{
		if ($position < 0 || $position >= $this->n)
		{
			echo "\n Position are not valid \n";
		}
		else
		{
			// Display given data and position
			echo "\n\n Update ".$data. " at position ".$position. " \n";
			if ($arr[$position] == $data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				$difference = $data - $arr[$position];
				// Set new value
				$arr[$position] = $data;
				// Perform tree update
				$this->updateElement(0, $this->n - 1, $position, $difference, 0);
			}
		}
	}
	// 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); // Sum query A
	// front = 2, tail = 7
	$task->nodeSum(2, 7); // Sum query B
	// front = 0, tail = 3
	$task->nodeSum(0, 3);
	// Update info
	$data = 4;
	$position = 5; // Perform update operation
	$task->updateRequest($arr, $position, $data); // Sum query C
	// front = 2, tail = 7
	$task->nodeSum(2, 7); // Sum query D
	// front = 0, tail = 3
	$task->nodeSum(0, 3);
}
main();

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
// Node Js Program
// Segment tree update query
class SegmentTree
{
	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);
	}
	treeSize()
	{
		// Calculate tree height
		var height = parseInt((Math.ceil(Math.log(this.n) / Math.log(2))));
		// returns the size of tree
		return 2 * parseInt(Math.pow(2, height)) - 1;
	}
	// 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);
		}
	}
	// Perform update operation
	updateElement(front, tail, position, difference, current)
	{
		// When position is outside the range
		if (position < front || position > tail)
		{
			return;
		}
		// Update new value
		this.node[current] = this.node[current] + difference;
		if (front < tail)
		{
			// Find middle node
			var mid = front + parseInt((tail - front) / 2);
			// Visit left subtree
			this.updateElement(front, mid, position, difference, 2 * current + 1);
			// Visit right subtree
			this.updateElement(mid + 1, tail, position, difference, 2 * current + 2);
		}
	}
	// Handles the request to update new element at given position
	updateRequest(arr, position, data)
	{
		if (position < 0 || position >= this.n)
		{
			process.stdout.write("\n Position are not valid \n");
		}
		else
		{
			// Display given data and position
			process.stdout.write("\n\n Update " + data + " at position " + position + " \n");
			if (arr[position] == data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				var difference = data - arr[position];
				// Set new value
				arr[position] = data;
				// Perform tree update
				this.updateElement(0, this.n - 1, position, difference, 0);
			}
		}
	}
	// 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);
	// Sum query A
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query B
	// front = 0, tail = 3
	task.nodeSum(0, 3);
	// Update info
	var data = 4;
	var position = 5;
	// Perform update operation
	// Test
	task.updateRequest(arr, position, data);
	// Sum query C
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query D
	// front = 0, tail = 3
	task.nodeSum(0, 3);
}
main();

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
import math
#  Python 3 Program 
#  Segment tree update query
class SegmentTree :
	
	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)
	
	def treeSize(self) :
		#  Calculate tree height 
		height = int((math.ceil(math.log(self.n) / math.log(2))))
		#  returns the size of tree
		return 2 * int(math.pow(2, height)) - 1
	
	#  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 = "")
		
	
	#  Perform update operation
	def updateElement(self, front, tail, position, difference, current) :
		if (position < front or position > tail) :
			#  When position is outside the range
			return
		
		#  Update new value
		self.node[current] = self.node[current] + difference
		if (front < tail) :
			#  Find middle node
			mid = front + int((tail - front) / 2)
			#  Visit left subtree
			self.updateElement(front, mid, position, difference, 2 * current + 1)
			#  Visit right subtree
			self.updateElement(mid + 1, tail, position, difference, 2 * current + 2)
		
	
	#  Handles the request to update new element at given position
	def updateRequest(self, arr, position, data) :
		if (position < 0 or position >= self.n) :
			print("\n Position are not valid ")
		else :
			#  Display given data and position
			print("\n\n Update ", data ," at position ", position ," ")
			if (arr[position] == data) :
				#  When update value is similar
				return
			else :
				#  Get difference
				difference = data - arr[position]
				#  Set new value          
				arr[position] = data
				#  Perform tree update
				self.updateElement(0, self.n - 1, position, difference, 0)
			
		
	
	#  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) #  Sum query A
	#  front = 2, tail = 7
	task.nodeSum(2, 7) #  Sum query B
	#  front = 0, tail = 3
	task.nodeSum(0, 3)
	#  Update info
	data = 4
	position = 5 #  Perform update operation 
	#  Test
	task.updateRequest(arr, position, data) #  Sum query C
	#  front = 2, tail = 7
	task.nodeSum(2, 7) #  Sum query D
	#  front = 0, tail = 3
	task.nodeSum(0, 3)

if __name__ == "__main__": main()

Output

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

 Update  4  at position  5

 Given range ( 2 ,  7 )
 Sum :  26
 Given range ( 0 ,  3 )
 Sum :  17
#  Ruby Program 
#  Segment tree update query
class SegmentTree  
	# Define the accessor and reader of class SegmentTree  
	attr_reader :node, :size, :n
	attr_accessor :node, :size, :n
 
	
	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

	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

	#  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

	#  Perform update operation
	def updateElement(front, tail, position, difference, current) 
		if (position < front || position > tail) 
			#  When position is outside the range
			return
		end

		#  Update new value
		self.node[current] = self.node[current] + difference
		if (front < tail) 
			#  Find middle node
			mid = front + (tail - front) / 2
			#  Visit left subtree
			self.updateElement(front, mid, position, difference, 2 * current + 1)
			#  Visit right subtree
			self.updateElement(mid + 1, tail, position, difference, 2 * current + 2)
		end

	end

	#  Handles the request to update new element at given position
	def updateRequest(arr, position, data) 
		if (position < 0 || position >= self.n) 
			print("\n Position are not valid \n")
		else 
			#  Display given data and position
			print("\n\n Update ", data ," at position ", position ," \n")
			if (arr[position] == data) 
				#  When update value is similar
				return
			else 
				#  Get difference
				difference = data - arr[position]
				#  Set new value          
				arr[position] = data
				#  Perform tree update
				self.updateElement(0, self.n - 1, position, difference, 0)
			end

		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)
	#  Sum query A
	#  front = 2, tail = 7
	task.nodeSum(2, 7)
	#  Sum query B
	#  front = 0, tail = 3
	task.nodeSum(0, 3)
	#  Update info
	data = 4
	position = 5
	#  Perform update operation 
	#  Test
	task.updateRequest(arr, position, data)
	#  Sum query C
	#  front = 2, tail = 7
	task.nodeSum(2, 7)
	#  Sum query D
	#  front = 0, tail = 3
	task.nodeSum(0, 3)
end

main()

Output

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

 Update 4 at position 5 

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
// Scala Program
// Segment tree update query
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);
		}
	}
	// Perform update operation
	def updateElement(front: Int, tail: Int, position: Int, difference: Int, current: Int): Unit = {
		// When position is outside the range
		if (position < front || position > tail)
		{
			return;
		}
		// Update new value
		this.node(current) = this.node(current) + difference;
		if (front < tail)
		{
			// Find middle node
			var mid: Int = front + ((tail - front) / 2).toInt;
			// Visit left subtree
			this.updateElement(front, mid, position, difference, 2 * current + 1);
			// Visit right subtree
			this.updateElement(mid + 1, tail, position, difference, 2 * current + 2);
		}
	}
	// Handles the request to update new element at given position
	def updateRequest(arr: Array[Int], position: Int, data: Int): Unit = {
		if (position < 0 || position >= this.n)
		{
			print("\n Position are not valid \n");
		}
		else
		{
			// Display given data and position
			print("\n\n Update " + data + " at position " + position + " \n");
			if (arr(position) == data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				var difference: Int = data - arr(position);
				// Set new value
				arr(position) = data;
				// Perform tree update
				this.updateElement(0, this.n - 1, position, difference, 0);
			}
		}
	}
	// 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);
		// Sum query A
		// front = 2, tail = 7
		task.nodeSum(2, 7);
		// Sum query B
		// front = 0, tail = 3
		task.nodeSum(0, 3);
		// Update info
		var data: Int = 4;
		var position: Int = 5;
		// Perform update operation
		// Test
		task.updateRequest(arr, position, data);
		// Sum query C
		// front = 2, tail = 7
		task.nodeSum(2, 7);
		// Sum query D
		// front = 0, tail = 3
		task.nodeSum(0, 3);
	}
}

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17
import Foundation
// Swift 4 Program
// Segment tree update query
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: "");
		}
	}
	// Perform update operation
	func updateElement(_ front: Int, _ tail: Int, _ position: Int, _ difference: Int, _ current: Int)
	{
		// When position is outside the range
		if (position < front || position > tail)
		{
			return;
		}
		// Update new value
		self.node[current] = self.node[current] + difference;
		if (front < tail)
		{
			// Find middle node
			let mid: Int = front + (tail - front) / 2;
			// Visit left subtree
			self.updateElement(front, mid, position, difference, 2 * current + 1);
			// Visit right subtree
			self.updateElement(mid + 1, tail, position, difference, 2 * current + 2);
		}
	}
	// Handles the request to update new element at given position
	func updateRequest(_ arr: inout[Int], _ position: Int, _ data: Int)
	{
		if (position < 0 || position >= self.n)
		{
			print("\n Position are not valid ");
		}
		else
		{
			// Display given data and position
			print("\n\n Update ", data ," at position ", position ," ");
			if (arr[position] == data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				let difference: Int = data - arr[position];
				// Set new value
				arr[position] = data;
				// Perform tree update
				self.updateElement(0, self.n - 1, position, difference, 0);
			}
		}
	}
	// Display array elements
	func printElement(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
}
func main()
{
	var 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);
	// Sum query A
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query B
	// front = 0, tail = 3
	task.nodeSum(0, 3);
	// Update info
	let data: Int = 4;
	let position: Int = 5;
	// Perform update operation
	// Test
	task.updateRequest(&arr, position, data);
	// Sum query C
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query D
	// front = 0, tail = 3
	task.nodeSum(0, 3);
}
main();

Output

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

 Update  4  at position  5

 Given range ( 2 ,  7 )
 Sum :  26
 Given range ( 0 ,  3 )
 Sum :  17
// Kotlin Program
// Segment tree update query
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);
		}
	}
	// Perform update operation
	fun updateElement(front: Int, tail: Int, position: Int, difference: Int, current: Int): Unit
	{
		// When position is outside the range
		if (position < front || position > tail)
		{
			return;
		}
		// Update new value
		this.node[current] = this.node[current] + difference;
		if (front < tail)
		{
			// Find middle node
			var mid: Int = front + (tail - front) / 2;
			// Visit left subtree
			this.updateElement(front, mid, position, difference, 2 * current + 1);
			// Visit right subtree
			this.updateElement(mid + 1, tail, position, difference, 2 * current + 2);
		}
	}
	// Handles the request to update new element at given position
	fun updateRequest(arr: Array < Int > , position: Int, data: Int): Unit
	{
		if (position < 0 || position >= this.n)
		{
			print("\n Position are not valid \n");
		}
		else
		{
			// Display given data and position
			print("\n\n Update " + data + " at position " + position + " \n");
			if (arr[position] == data)
			// When update value is similar
			{
				return;
			}
			else
			{
				// Get difference
				var difference: Int = data - arr[position];
				// Set new value
				arr[position] = data;
				// Perform tree update
				this.updateElement(0, this.n - 1, position, difference, 0);
			}
		}
	}
	// 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);
	// Sum query A
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query B
	// front = 0, tail = 3
	task.nodeSum(0, 3);
	// Update info
	var data: Int = 4;
	var position: Int = 5;
	// Perform update operation
	// Test
	task.updateRequest(arr, position, data);
	// Sum query C
	// front = 2, tail = 7
	task.nodeSum(2, 7);
	// Sum query D
	// front = 0, tail = 3
	task.nodeSum(0, 3);
}

Output

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

 Update 4 at position 5

 Given range (2, 7)
 Sum : 26
 Given range (0, 3)
 Sum : 17

Resultant Output Explanation

  • The initial array is printed using the printElement function.
  • Sum queries A and B are performed using the nodeSum function and their results are printed.
  • An update query is executed to change the value at position 5 to 4.
  • Sum queries C and D are performed again after the update, and the results are printed.

The output results are explained in the Example Scenario section above.

Time Complexity

  • Constructing the segment tree takes O(n) time.
  • Each sum query and update query takes O(log n) time due to the binary tree structure.
  • The total time complexity of processing q queries (sum and update) is O(q * log n).
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