Segmentbaum | Satz 1 (Summe des angegebenen Bereichs)
Betrachten wir das folgende Problem, um Segmentbäume zu verstehen.
Wir haben ein Array arr[0 . . . n-1]. Wir sollten in der Lage sein,
1 die Summe der Elemente von Index l bis r zu finden, wobei 0 <= l <= r <= n-1
2 den Wert eines angegebenen Elements des Arrays in einen neuen Wert x zu ändern. Wir müssen arr[i] = x ausführen, wobei 0 <= i <= n-1.
Eine einfache Lösung besteht darin, eine Schleife von l nach r auszuführen und die Summe der Elemente im angegebenen Bereich zu berechnen. Um einen Wert zu aktualisieren, führen Sie einfach arr[i] = x aus. Die erste Operation benötigt O(n) Zeit und die zweite Operation O(1) Zeit.
Eine andere Lösung besteht darin, ein weiteres Array zu erstellen und die Summe von start bis i am i-ten Index in diesem Array zu speichern. Die Summe eines gegebenen Bereichs kann jetzt in O(1)-Zeit berechnet werden, aber der Aktualisierungsvorgang dauert jetzt O(n)-Zeit. Dies funktioniert gut, wenn die Anzahl der Abfragevorgänge groß ist und nur sehr wenige Aktualisierungen vorgenommen werden.
Was ist, wenn die Anzahl der Abfragen und Aktualisierungen gleich ist? Können wir beide Operationen in O(log n)-Zeit ausführen, sobald das Array gegeben ist? Wir können einen Segmentbaum verwenden, um beide Operationen in O(Logn)-Zeit auszuführen.
Darstellung von Segmentbäumen
1. Blattknoten sind die Elemente des Eingabearrays.
2. Jeder interne Node repräsentiert eine gewisse Verschmelzung der Blattknoten. Das Zusammenführen kann für verschiedene Probleme unterschiedlich sein. Für dieses Problem ist das Zusammenführen die Summe der Blätter unter einem Node.
Eine Array-Darstellung des Baums wird verwendet, um Segmentbäume darzustellen. Für jeden Node am Index i befindet sich das linke Kind am Index 2*i+1, das rechte Kind an 2*i+2 und das Elternteil an ⌊(i – 1) / 2⌋ .
Wie sieht der obige Segmentbaum im Speicher aus?
Wie Heap wird auch der Segmentbaum als Array dargestellt. Der Unterschied besteht hier darin, dass es sich nicht um einen vollständigen Binärbaum handelt. Es ist eher ein vollständiger binärer Baum (jeder Node hat 0 oder 2 Kinder) und alle Ebenen sind gefüllt, möglicherweise mit Ausnahme der letzten Ebene. Im Gegensatz zu Heap kann die letzte Ebene Lücken zwischen Node aufweisen. Nachfolgend sind die Werte im Segmentbaumarray für das obige Diagramm aufgeführt.
Unten ist die Speicherdarstellung des Segmentbaums für das Eingabearray {1, 3, 5, 7, 9, 11}
st[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}
Auf die Dummy-Werte wird niemals zugegriffen und sie haben keine Verwendung. Dies ist aufgrund der einfachen Array-Darstellung eine gewisse Platzverschwendung. Wir können diese Verschwendung durch einige clevere Implementierungen optimieren, aber der Code für Summe und Aktualisierung wird komplexer.
Konstruktion eines Segmentbaums aus einem gegebenen Array
Wir beginnen mit einem Segment arr[0 . . . n-1]. und jedes Mal, wenn wir das aktuelle Segment in zwei Hälften teilen (wenn es noch kein Segment der Länge 1 geworden ist), und dann dieselbe Prozedur für beide Hälften aufrufen, und für jedes solche Segment speichern wir die Summe im entsprechenden Node.
Alle Ebenen des konstruierten Segmentbaums werden bis auf die letzte Ebene vollständig gefüllt. Außerdem wird der Baum ein vollständiger binärer Baum sein , da wir Segmente auf jeder Ebene immer in zwei Hälften teilen. Da der konstruierte Baum immer ein vollständiger binärer Baum mit n Blättern ist, gibt es n-1 interne Node. Die Gesamtzahl der Node ist also 2*n – 1. Beachten Sie, dass dies keine Dummy-Node enthält.
Wie groß ist die Gesamtgröße des Arrays, das den Segmentbaum darstellt?
Wenn n eine Potenz von 2 ist, dann gibt es keine Dummy-Node. Die Größe des Segmentbaums ist also 2n-1 (n Blattknoten und n-1 interne Node). Wenn n keine Potenz von 2 ist, dann ist die Größe des Baums 2*x – 1, wobei x die kleinste Potenz von 2 größer als n ist. Wenn beispielsweise n = 10 ist, beträgt die Größe des Arrays, das den Segmentbaum darstellt, 2*16-1 = 31.
Eine alternative Erklärung für die Größe basiert auf der Höhe. Die Höhe des Segmentbaums beträgt ⌈log₂n⌉ . Da der Baum mithilfe eines Arrays dargestellt wird und die Beziehung zwischen übergeordneten und untergeordneten Indizes beibehalten werden muss, beträgt die Größe des für den Segmentbaum zugewiesenen Speichers 2 * 2 ⌈log 2 n⌉ – 1 .
Abfrage der Summe des gegebenen Bereichs
Sobald der Baum erstellt ist, wie man die Summe unter Verwendung des konstruierten Segmentbaums erhält. Das Folgende ist der Algorithmus, um die Summe der Elemente zu erhalten.
int getSum(node, l, r)
{
if the range of the node is within l and r
return value in the node
else if the range of the node is completely outside l and r
return 0
else
return getSum(node's left child, l, r) +
getSum(node's right child, l, r)
}
Aktualisieren eines Werts
Wie bei Baumkonstruktionen und Abfrageoperationen kann auch die Aktualisierung rekursiv erfolgen. Wir erhalten einen Index, der aktualisiert werden muss. Sei diff der hinzuzufügende Wert. Wir beginnen bei der Wurzel des Segmentbaums und fügen diff zu allen Node hinzu, die in ihrem Bereich einen Index angegeben haben. Wenn ein Node keinen bestimmten Index in seinem Bereich hat, nehmen wir keine Änderungen an diesem Node vor.
Implementierung:
Es folgt die Implementierung des Segmentbaums. Das Programm implementiert den Aufbau eines Segmentbaums für ein beliebiges gegebenes Array. Es implementiert auch Abfrage- und Aktualisierungsoperationen.
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>
Ausgabe:
Sum of values in given range = 15 Updated sum of values in given range = 22
Zeitkomplexität:
Die Zeitkomplexität für die Baumkonstruktion ist O(n). Es gibt insgesamt 2n-1 Node, und der Wert jedes Nodes wird nur einmal bei der Baumkonstruktion berechnet.
Die Zeitkomplexität der Abfrage beträgt O(Logn). Um eine Summe abzufragen, verarbeiten wir höchstens vier Node auf jeder Ebene und die Anzahl der Ebenen ist O(Logn).
Die Zeitkomplexität der Aktualisierung ist ebenfalls O(Logn). Um einen Blattwert zu aktualisieren, verarbeiten wir einen Node auf jeder Ebene und die Anzahl der Ebenen ist O(Logn).
Segmentbaum | Satz 2 (Bereichsminimum-Abfrage)
Referenzen:
IIT Kanpur-Papier.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .