Módulo de árbol de segmentos en Python

Requisito previo: implementación del árbol 
de segmentos Un árbol de segmentos es una estructura de datos que permite a los programadores resolver consultas de rango sobre el arreglo dado de manera efectiva y modificar los valores del arreglo. Básicamente, Segment Tree es una estructura de datos muy flexible y eficiente y una gran cantidad de problemas se pueden resolver con la ayuda de segmentos de árboles.

El módulo de árbol de segmentos de Python también se usa para resolver problemas de consulta de rango. Realiza varias operaciones en un rango dado como sum , max , min y actualizar el valor en un rango. Estos módulos ayudan a evitar la implementación del árbol de segmentación, ya que podemos usar directamente la función del árbol de segmentos para realizar todas las operaciones. 
Por lo general, reduce el estrés de implementar el árbol de segmentos.

Instalación de la biblioteca:

pip install segment-tree

Funciones del árbol de segmentos:

• Consulta: es la función principal del árbol de segmentos que realiza operaciones como encontrar el número máximo en un rango, encontrar el número mínimo en un rango y encontrar la suma de un rango dado. Toma 3 argumentos como entrada que son start_index (es decir, desde donde comenzará el rango), End_index (es decir, hasta qué rango de índice finaliza) y la operación a realizar.
  Sintaxis: 

obj.query(Start_index, End_index, operation_name)

• Actualizar: la segunda función principal del árbol de segmentos es la actualización, que actualizará el valor de un índice particular dentro del rango. Reemplazará el valor existente presente en ese índice con el nuevo valor.
  Sintaxis:

obj.update(index, value)

Ejemplo 1:

from segment_tree import SegmentTree
 
# an array with some elements
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
 
# here we are fitting our array
# into segment tree where t is
# taken as object of segment tree
# t will be used for performing
# operations on that segmentTree
 
t = SegmentTree(arr)
 
# here we are finding value
# of maximum number in a range
a = t.query(2, 9, "max")
print("The maximum value of this range is : ", a)
 
 
# here we are finding the value
# of minimum number in a range
a = t.query(2, 9, "min")
print("The minimum value of this range is : ", a)
 
 
# here we are finding the value
# of sum of a range
a = t.query(2, 7, "sum")
print("The sum of this range is : ", a)
 
 
# here we are updating the value
# of a particular index
t.update(2, 25)
 
# it will replace the value of
# index '2' with 25
print("The updated array is : ", arr)

Producción: 

The maximum value of this range is :  10
The minimum value of this range is :  3
The sum of this range is :  33
The updated array is :  [1, 2, 25, 4, 5, 6, 7, 8, 9, 10, 11]

Ejemplo 2:

from segment_tree import SegmentTree
 
 
# an array with some elements
arr = [14, 28, 55, 105, 78, 4, 24, 99, 48, 200]
 
# here we are fitting our array
# into segment tree where t is
# taken as object of segment tree
# t will be used for performing
# operations on that segmentTree
 
t = SegmentTree(arr)
 
# here we are finding value of
# maximum number in a range
a = t.query(0, 9, "max")
print("The maximum value of this range is : ", a)
 
# here we are finding value of
# minimum number in a range
a = t.query(0, 9, "min")
print("The minimum value of this range is : ", a)
 
# here we are finding value
# of sum of a range
a = t.query(0, 9, "sum")
print("The sum of this range is : ", a)
 
# here we are updating the value
# of a particular index
t.update(5, 0)
print("The updated array is : ", arr)
 
 
# here we are finding value of
# sum of a range
a = t.query(1, 5, "sum")
print("The sum of this range is : ", a)
 
# here we are updating the value
# of a particular index
t.update(4, 10)
print("The updated array is : ", arr)

Producción:

The maximum value of this range is :  200
The minimum value of this range is :  4
The sum of this range is :  655
The updated array is :  [14, 28, 55, 105, 78, 0, 24, 99, 48, 200]
The sum of this range is :  266
The updated array is :  [14, 28, 55, 105, 10, 0, 24, 99, 48, 200]