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:
- Sum Query
Find the sum of elements within a given range [front, tail].
- 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 AFinding the sum of elements in the range [2, 7].
- Elements: 1, 9, 4, 8, 7, 1
- Sum: 1 + 9 + 4 + 8 + 7 + 1 = 30
Finding the sum of elements in the range [0, 3].
- Elements: 2, 5, 1, 9
- Sum: 2 + 5 + 1 + 9 = 17
Updating the element at position 5 to the value 4.
- Previous value at position 5: 8
- New value at position 5: 4
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
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
-
The
constructTree
function constructs the segment tree by recursively dividing the array segments until reaching individual elements. -
The
makeTree
function allocates memory and constructs the segment tree. -
The
findSum
function is responsible for finding the sum of elements within a given range using recursion. -
The
updateElement
function handles element updates in the segment tree while maintaining the integrity of the tree structure. -
The
updateRequest
function updates an element in the original array and propagates the change to the segment tree. -
The
nodeSum
function handles sum queries by calling thefindSum
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).
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