Consideremos el siguiente problema para comprender los árboles de segmentos.
Tenemos una array arr[0 . . . n-1]. Deberíamos ser capaces de
- Encuentre la suma de elementos del índice l a r donde 0 <= l <= r <= n-1
- Cambia el valor de un elemento específico de la array a un nuevo valor x. Necesitamos hacer arr[i] = x donde 0 <= i <= n-1.
Una solución simple es ejecutar un ciclo de l a r y calcular la suma de los elementos en el rango dado. Para actualizar un valor, simplemente haga arr[i] = x. La primera operación toma el tiempo O(n) y la segunda operación toma el tiempo O(1).
C++
// C++ program to show segment tree operations like construction, query
// and update
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the sum of values in the given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(st, ss, mid, qs, qe, 2*si+1) +
getSumUtil(st, mid+1, se, qs, qe, 2*si+2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This index is
in the input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update
// the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n-1)
{
cout<<"Invalid Input";
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n-1, i, diff, 0);
}
// Return sum of elements in range from index qs (query start)
// to qe (query end). It mainly uses getSumUtil()
int getSum(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
cout<<"Invalid Input";
return -1;
}
return getSumUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) +
constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for the segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
// Allocate memory
int *st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *st = constructST(arr, n);
// Print sum of values in array from index 1 to 3
cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl;
// Update: set arr[1] = 10 and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
cout<<"Updated sum of values in given range = "
<<getSum(st, n, 1, 3)<<endl;
return 0;
}
//This code is contributed by rathbhupendra
C
// C program to show segment tree operations like construction, query
// and update
#include <stdio.h>
#include <math.h>
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the sum of values in given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(st, ss, mid, qs, qe, 2*si+1) +
getSumUtil(st, mid+1, se, qs, qe, 2*si+2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This index is
in the input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update
// the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n-1)
{
printf("Invalid Input");
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n-1, i, diff, 0);
}
// Return sum of elements in range from index qs (query start)
// to qe (query end). It mainly uses getSumUtil()
int getSum(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
printf("Invalid Input");
return -1;
}
return getSumUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) +
constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for the segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
// Allocate memory
int *st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *st = constructST(arr, n);
// Print sum of values in array from index 1 to 3
printf("Sum of values in given range = %dn",
getSum(st, n, 1, 3));
// Update: set arr[1] = 10 and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find sum after the value is updated
printf("Updated sum of values in given range = %dn",
getSum(st, n, 1, 3));
return 0;
}
Java
// Java Program to show segment tree operations like construction,
// query and update
class SegmentTree
{
int st[]; // The array that stores segment tree nodes
/* Constructor to construct segment tree from given array. This
constructor allocates memory for segment tree and calls
constructSTUtil() to fill the allocated memory */
SegmentTree(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
//Maximum size of segment tree
int max_size = 2 * (int) Math.pow(2, x) - 1;
st = new int[max_size]; // Memory allocation
constructSTUtil(arr, 0, n - 1, 0);
}
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) {
return s + (e - s) / 2;
}
/* A recursive function to get the sum of values in given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getSumUtil()
i --> index of the element to be updated. This index is in
input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update the
// value of the node and its children
st[si] = st[si] + diff;
if (se != ss) {
int mid = getMid(ss, se);
updateValueUtil(ss, mid, i, diff, 2 * si + 1);
updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1) {
System.out.println("Invalid Input");
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(0, n - 1, i, diff, 0);
}
// Return sum of elements in range from index qs (query start) to
// qe (query end). It mainly uses getSumUtil()
int getSum(int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe) {
System.out.println("Invalid Input");
return -1;
}
return getSumUtil(0, n - 1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) +
constructSTUtil(arr, mid + 1, se, si * 2 + 2);
return st[si];
}
// Driver program to test above functions
public static void main(String args[])
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = arr.length;
SegmentTree tree = new SegmentTree(arr, n);
// Build segment tree from given array
// Print sum of values in array from index 1 to 3
System.out.println("Sum of values in given range = " +
tree.getSum(n, 1, 3));
// Update: set arr[1] = 10 and update corresponding segment
// tree nodes
tree.updateValue(arr, n, 1, 10);
// Find sum after the value is updated
System.out.println("Updated sum of values in given range = " +
tree.getSum(n, 1, 3));
}
}
//This code is contributed by Ankur Narain Verma
Python3
# Python3 program to show segment tree operations like
# construction, query and update
from math import ceil, log2;
# A utility function to get the
# middle index from corner indexes.
def getMid(s, e) :
return s + (e -s) // 2;
""" A recursive function to get the sum of values
in the given range of the array. The following
are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree.
Initially 0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment
represented by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range """
def getSumUtil(st, ss, se, qs, qe, si) :
# If segment of this node is a part of given range,
# then return the sum of the segment
if (qs <= ss and qe >= se) :
return st[si];
# If segment of this node is
# outside the given range
if (se < qs or ss > qe) :
return 0;
# If a part of this segment overlaps
# with the given range
mid = getMid(ss, se);
return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);
""" A recursive function to update the nodes
which have the given index in their range.
The following are parameters st, si, ss and se
are same as getSumUtil()
i --> index of the element to be updated.
This index is in the input array.
diff --> Value to be added to all nodes
which have i in range """
def updateValueUtil(st, ss, se, i, diff, si) :
# Base Case: If the input index lies
# outside the range of this segment
if (i < ss or i > se) :
return;
# If the input index is in range of this node,
# then update the value of the node and its children
st[si] = st[si] + diff;
if (se != ss) :
mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i,
diff, 2 * si + 1);
updateValueUtil(st, mid + 1, se, i,
diff, 2 * si + 2);
# The function to update a value in input array
# and segment tree. It uses updateValueUtil()
# to update the value in segment tree
def updateValue(arr, st, n, i, new_val) :
# Check for erroneous input index
if (i < 0 or i > n - 1) :
print("Invalid Input", end = "");
return;
# Get the difference between
# new value and old value
diff = new_val - arr[i];
# Update the value in array
arr[i] = new_val;
# Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
# Return sum of elements in range from
# index qs (query start) to qe (query end).
# It mainly uses getSumUtil()
def getSum(st, n, qs, qe) :
# Check for erroneous input values
if (qs < 0 or qe > n - 1 or qs > qe) :
print("Invalid Input", end = "");
return -1;
return getSumUtil(st, 0, n - 1, qs, qe, 0);
# A recursive function that constructs
# Segment Tree for array[ss..se].
# si is index of current node in segment tree st
def constructSTUtil(arr, ss, se, st, si) :
# If there is one element in array,
# store it in current node of
# segment tree and return
if (ss == se) :
st[si] = arr[ss];
return arr[ss];
# If there are more than one elements,
# then recur for left and right subtrees
# and store the sum of values in this node
mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) +
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);
return st[si];
""" Function to construct segment tree
from given array. This function allocates memory
for segment tree and calls constructSTUtil() to
fill the allocated memory """
def constructST(arr, n) :
# Allocate memory for the segment tree
# Height of segment tree
x = (int)(ceil(log2(n)));
# Maximum size of segment tree
max_size = 2 * (int)(2**x) - 1;
# Allocate memory
st = [0] * max_size;
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
# Return the constructed segment tree
return st;
# Driver Code
if __name__ == "__main__" :
arr = [1, 3, 5, 7, 9, 11];
n = len(arr);
# Build segment tree from given array
st = constructST(arr, n);
# Print sum of values in array from index 1 to 3
print("Sum of values in given range = ",
getSum(st, n, 1, 3));
# Update: set arr[1] = 10 and update
# corresponding segment tree nodes
updateValue(arr, st, n, 1, 10);
# Find sum after the value is updated
print("Updated sum of values in given range = ",
getSum(st, n, 1, 3), end = "");
# This code is contributed by AnkitRai01
C#
// C# Program to show segment tree
// operations like construction,
// query and update
using System;
class SegmentTree
{
int []st; // The array that stores segment tree nodes
/* Constructor to construct segment
tree from given array. This constructor
allocates memory for segment tree and calls
constructSTUtil() to fill the allocated memory */
SegmentTree(int []arr, int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int) (Math.Ceiling(Math.Log(n) / Math.Log(2)));
//Maximum size of segment tree
int max_size = 2 * (int) Math.Pow(2, x) - 1;
st = new int[max_size]; // Memory allocation
constructSTUtil(arr, 0, n - 1, 0);
}
// A utility function to get the
// middle index from corner indexes.
int getMid(int s, int e)
{
return s + (e - s) / 2;
}
/* A recursive function to get
the sum of values in given range
of the array. The following
are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the
segment tree. Initially
0 is passed as root is
always at index 0
ss & se --> Starting and ending indexes
of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getSumUtil(int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part
// of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment
// overlaps with the given range
int mid = getMid(ss, se);
return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}
/* A recursive function to update
the nodes which have the given
index in their range. The following
are parameters st, si, ss and se
are same as getSumUtil() i --> index
of the element to be updated. This
index is in input array. diff --> Value
to be added to all nodes which have i in range */
void updateValueUtil(int ss, int se, int i,
int diff, int si)
{
// Base Case: If the input index
// lies outside the range of this segment
if (i < ss || i > se)
return;
// If the input index is in range of
// this node, then update the value
// of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(ss, mid, i, diff, 2 * si + 1);
updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
}
}
// The function to update a value
// in input array and segment tree.
// It uses updateValueUtil() to
// update the value in segment tree
void updateValue(int []arr, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
Console.WriteLine("Invalid Input");
return;
}
// Get the difference between
// new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(0, n - 1, i, diff, 0);
}
// Return sum of elements in range
// from index qs (query start) to
// qe (query end). It mainly uses getSumUtil()
int getSum(int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
Console.WriteLine("Invalid Input");
return -1;
}
return getSumUtil(0, n - 1, qs, qe, 0);
}
// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int []arr, int ss, int se, int si)
{
// If there is one element in array,
// store it in current node of
// segment tree and return
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the sum of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) +
constructSTUtil(arr, mid + 1, se, si * 2 + 2);
return st[si];
}
// Driver code
public static void Main()
{
int []arr = {1, 3, 5, 7, 9, 11};
int n = arr.Length;
SegmentTree tree = new SegmentTree(arr, n);
// Build segment tree from given array
// Print sum of values in array from index 1 to 3
Console.WriteLine("Sum of values in given range = " +
tree.getSum(n, 1, 3));
// Update: set arr[1] = 10 and update
// corresponding segment tree nodes
tree.updateValue(arr, n, 1, 10);
// Find sum after the value is updated
Console.WriteLine("Updated sum of values in given range = " +
tree.getSum(n, 1, 3));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript Program to show segment tree
// operations like construction,
// query and update
class SegmentTree {
/* Constructor to construct segment
tree from given array. This constructor
allocates memory for segment tree and calls
constructSTUtil() to fill the allocated memory */
constructor(arr, n) {
// Allocate memory for segment tree
// Height of segment tree
var x = parseInt(Math.ceil(Math.log(n) / Math.log(2)));
//Maximum size of segment tree
var max_size = 2 * parseInt(Math.pow(2, x) - 1);
this.st = new Array(max_size).fill(0); // Memory allocation
this.constructSTUtil(arr, 0, n - 1, 0);
}
// A utility function to get the
// middle index from corner indexes.
getMid(s, e) {
return parseInt(s + (e - s) / 2);
}
/* A recursive function to get
the sum of values in given range
of the array. The following
are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the
segment tree. Initially
0 is passed as root is
always at index 0
ss & se --> Starting and ending indexes
of the segment represented
by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
getSumUtil(ss, se, qs, qe, si) {
// If segment of this node is a part
// of given range, then return
// the sum of the segment
if (qs <= ss && qe >= se) return this.st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe) return 0;
// If a part of this segment
// overlaps with the given range
var mid = this.getMid(ss, se);
return (
this.getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
this.getSumUtil(mid + 1, se, qs, qe, 2 * si + 2)
);
}
/* A recursive function to update
the nodes which have the given
index in their range. The following
are parameters st, si, ss and se
are same as getSumUtil() i --> index
of the element to be updated. This
index is in input array. diff --> Value
to be added to all nodes which have i in range */
updateValueUtil(ss, se, i, diff, si) {
// Base Case: If the input index
// lies outside the range of this segment
if (i < ss || i > se) return;
// If the input index is in range of
// this node, then update the value
// of the node and its children
this.st[si] = this.st[si] + diff;
if (se != ss) {
var mid = this.getMid(ss, se);
this.updateValueUtil(ss, mid, i, diff, 2 * si + 1);
this.updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
}
}
// The function to update a value
// in input array and segment tree.
// It uses updateValueUtil() to
// update the value in segment tree
updateValue(arr, n, i, new_val) {
// Check for erroneous input index
if (i < 0 || i > n - 1) {
document.write("Invalid Input");
return;
}
// Get the difference between
// new value and old value
var diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
this.updateValueUtil(0, n - 1, i, diff, 0);
}
// Return sum of elements in range
// from index qs (query start) to
// qe (query end). It mainly uses getSumUtil()
getSum(n, qs, qe) {
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe) {
document.write("Invalid Input");
return -1;
}
return this.getSumUtil(0, n - 1, qs, qe, 0);
}
// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
constructSTUtil(arr, ss, se, si) {
// If there is one element in array,
// store it in current node of
// segment tree and return
if (ss == se) {
this.st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the sum of values in this node
var mid = this.getMid(ss, se);
this.st[si] =
this.constructSTUtil(arr, ss, mid, si * 2 + 1) +
this.constructSTUtil(arr, mid + 1, se, si * 2 + 2);
return this.st[si];
}
}
// Driver code
var arr = [1, 3, 5, 7, 9, 11];
var n = arr.length;
var tree = new SegmentTree(arr, n);
// Build segment tree from given array
// Print sum of values in array from index 1 to 3
document.write(
"Sum of values in given range = "
+ tree.getSum(n, 1, 3) + "<br>"
);
// Update: set arr[1] = 10 and update
// corresponding segment tree nodes
tree.updateValue(arr, n, 1, 10);
// Find sum after the value is updated
document.write(
"Updated sum of values in given range = " +
tree.getSum(n, 1, 3) +
"<br>"
);
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA