Dada una array arr[0 . . . n-1]. Encuentre el máximo de elementos del índice l a r donde 0 <= l <= r <= n-1. Además, cambie 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 y luego encontrar el elemento máximo del rango dado con valores actualizados.
Ejemplo :
Input : {1, 3, 5, 7, 9, 11}
Maximum Query : L = 1, R = 3
update : set arr[1] = 8
Output :
Max of values in given range = 7
Updated max of values in given range = 8
Una solución simple es ejecutar un ciclo de l a r y calcular el máximo de 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).
Enfoque eficiente: aquí, necesitamos realizar operaciones en tiempo O (Inicio de sesión) para que podamos usar Segment Tree para realizar ambas operaciones en tiempo O (Inicio de sesión) .
Representación de árboles de segmentos
1. Los Nodes hoja son los elementos del arreglo de entrada.
2. Cada Node interno representa el máximo de todos sus hijos.
Se utiliza una representación de array de árbol para representar árboles de segmento. Para cada Node en el índice i, el hijo izquierdo está en el índice 2*i+1 , el hijo derecho en el índice 2*i+2 y el padre está en el índice (i-1)/2 .
Construcción del árbol de segmentos a partir de una array dada:
comenzamos con un segmento arr[0 . . . n-1], y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos el máximo valor en un Node de árbol de segmento. Todos los niveles del árbol de segmentos construido se llenarán por completo excepto el último nivel. Además, el árbol será un árbol binario completo porque siempre dividimos los segmentos en dos mitades en cada nivel. Dado que el árbol construido siempre es un árbol binario completo con n hojas, habrá n-1 Nodes internos. Entonces, el total de Nodes será 2*n – 1 . La altura del árbol de segmentos será log2n. Dado que el árbol se representa mediante una array y se debe mantener la relación entre los índices principal y secundario, el tamaño de la memoria asignada para el árbol de segmento será 2*( 2^ceil(log2n) ) – 1 .
Consulta del valor máximo del rango dado : una vez que se construye el árbol, a continuación se muestra el algoritmo para encontrar el máximo del rango dado.
node--> node number, l -->
query start index, r --> query end index;
int getMax(node, l, r)
{
if range of node is within l and r
return value of node
else if range of node is completely outside l and r
return -1
else
return max(getMax(node's left child, l, r),
getMax(node's right child, l, r))
}
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code for range maximum query and updates
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the
// middle index of given range.
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
node -> Index of current node in
the segment tree .
ss & se -> Starting and ending indexes
of the segment represented
by current node, i.e., st[node]
l & r -> Starting and ending indexes
of range query */
int MaxUtil(int* st, int ss, int se, int l,
int r, int node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
int mid = getMid(ss, se);
return max(MaxUtil(st, ss, mid, l, r,
2 * node + 1),
MaxUtil(st, mid + 1, se, l,
r, 2 * node + 2));
}
/* A recursive function to update the nodes
which have the given index in their range.
The following are parameters st, ss and
se are same as defined
above index -> index of the element
to be updated.*/
void updateValue(int arr[], int* st, int ss, int se,
int index, int value, int node)
{
if (index < ss || index > se)
{
cout << "Invalid Input" << endl;
return;
}
if (ss == se)
{
// update value in array and in segment tree
arr[index] = value;
st[node] = value;
}
else {
int mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st,
ss, mid, index,
value, 2 * node + 1);
else
updateValue(arr,
st, mid + 1, se,
index,
value, 2 * node + 2);
st[node] = max(st[2 * node + 1],
st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
int getMax(int* st, int n, int l, int r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r)
{
printf("Invalid Input");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 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 max of values in this node
int mid = getMid(ss, se);
st[si] = max(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.*/
int* constructST(int arr[], int n)
{
// 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 code
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 max of values in array
// from index 1 to 3
cout << "Max of values in given range = "
<< getMax(st, n, 1, 3) << endl;
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 1, 8, 0);
// Find max after the value is updated
cout << "Updated max of values in given range = "
<< getMax(st, n, 1, 3) << endl;
return 0;
}
Java
// Java code for range maximum query and updates
import java.io.*;
import java.util.*;
class GFG {
// A utility function to get the
// middle index of given range.
static 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
* node -> Index of current node in
* the segment tree.
* ss & se -> Starting and ending indexes
* of the segment represented
* by current node, i.e., st[node]
* l & r -> Starting and ending indexes
* of range query
*/
static int MaxUtil(int[] st, int ss,
int se, int l,
int r, int node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
int mid = getMid(ss, se);
return Math.max(
MaxUtil(st, ss, mid, l, r,
2 * node + 1),
MaxUtil(st, mid + 1, se, l, r,
2 * node + 2));
}
/*
* A recursive function to update the
nodes which have the given index in their
* range. The following are parameters
st, ss and se are same as defined above
* index -> index of the element to be updated.
*/
static void updateValue(int arr[], int[]
st, int ss,
int se, int index,
int value,
int node)
{
if (index < ss || index > se) {
System.out.println("Invalid Input");
return;
}
if (ss == se) {
// update value in array and in
// segment tree
arr[index] = value;
st[node] = value;
}
else {
int mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st, ss, mid,
index, value,
2 * node + 1);
else
updateValue(arr, st, mid + 1, se, index,
value, 2 * node + 2);
st[node] = Math.max(st[2 * node + 1],
st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
static int getMax(int[] st, int n, int l, int r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r) {
System.out.printf("Invalid Input\n");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
static 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 max of values in this node
int mid = getMid(ss, se);
st[si] = Math.max(
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.
*/
static int[] constructST(int arr[], int n)
{
// 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;
// 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 Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 7, 9, 11 };
int n = arr.length;
// Build segment tree from given array
int[] st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
System.out.println("Max of values in given range = "
+ getMax(st, n, 1, 3));
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 1, 8, 0);
// Find max after the value is updated
System.out.println(
"Updated max of values in given range = "
+ getMax(st, n, 1, 3));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 code for range maximum query and updates
from math import ceil, log
# A utility function to get the
# middle index of given range.
def getMid(s, 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
# node -> Index of current node in
# the segment tree .
# ss & se -> Starting and ending indexes
# of the segment represented
# by current node, i.e., st[node]
# l & r -> Starting and ending indexes
# of range query */
def MaxUtil(st, ss, se, l, r, node):
# If segment of this node is completely
# part of given range, then return
# the max of segment
if (l <= ss and r >= se):
return st[node]
# If segment of this node does not
# belong to given range
if (se < l or ss > r):
return -1
# If segment of this node is partially
# the part of given range
mid = getMid(ss, se)
return max(MaxUtil(st, ss, mid, l, r,
2 * node + 1),
MaxUtil(st, mid + 1, se, l,
r, 2 * node + 2))
#
# /* A recursive function to update the nodes which
# have the given index in their range. The following
# are parameters st, ss and se are same as defined
# above index -> index of the element to be updated.*/
def updateValue(arr, st, ss, se, index, value, node):
if (index < ss or index > se):
print("Invalid Input")
return
if (ss == se):
# update value in array and in segment tree
arr[index] = value
st[node] = value
else:
mid = getMid(ss, se)
if (index >= ss and index <= mid):
updateValue(arr, st, ss, mid, index,
value, 2 * node + 1)
else:
updateValue(arr, st, mid + 1, se,
index, value, 2 * node + 2)
st[node] = max(st[2 * node + 1],
st[2 * node + 2])
return
# Return max of elements in range from
# index l (query start) to r (query end).
def getMax(st, n, l, r):
# Check for erroneous input values
if (l < 0 or r > n - 1 or l > r):
printf("Invalid Input")
return -1
return MaxUtil(st, 0, n - 1, l, r, 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 max of values in this node
mid = getMid(ss, se)
st[si] = max(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.*/
def constructST(arr, n):
# Height of segment tree
x = ceil(log(n, 2))
# Maximum size of segment tree
max_size = 2 * pow(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)
# Prmax of values in array
# from index 1 to 3
print("Max of values= ", getMax(st, n, 1, 3))
# Update: set arr[1] = 8 and update
# corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 1, 8, 0)
# Find max after the value is updated
print("Updated values = ", getMax(st, n, 1, 3))
# This code is contributed by mohit kumar 29
C#
// C# code for range maximum query and updates
using System;
class GFG
{
// A utility function to get the
// middle index of given range.
static 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
* node -> Index of current node in
* the segment tree.
* ss & se -> Starting and ending indexes
* of the segment represented
* by current node, i.e., st[node]
* l & r -> Starting and ending indexes
* of range query
*/
static int MaxUtil(int[] st, int ss, int se,
int l, int r, int node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
{
return st[node];
}
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
{
return -1;
}
// If segment of this node is partially
// the part of given range
int mid = getMid(ss, se);
return Math.Max(MaxUtil(st, ss, mid, l, r, 2 * node + 1),
MaxUtil(st, mid + 1, se, l, r,2 * node + 2));
}
/*
* A recursive function to update the
nodes which have the given index in their
* range. The following are parameters
st, ss and se are same as defined above
* index -> index of the element to be updated.
*/
static void updateValue(int[] arr,int[] st, int ss,
int se, int index,
int value,int node)
{
if (index < ss || index > se)
{
Console.WriteLine("Invalid Input");
return ;
}
if (ss == se)
{
// update value in array and in
// segment tree
arr[index] = value;
st[node] = value;
}
else
{
int mid = getMid(ss, se);
if (index >= ss && index <= mid)
{
updateValue(arr, st, ss, mid, index,
value, 2 * node + 1);
}
else
{
updateValue(arr, st, mid + 1, se,
index,value, 2 * node + 2);
}
st[node] = Math.Max(st[2 * node + 1],
st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
static int getMax(int[] st, int n, int l, int r)
{
// Check for erroneous input values
if(l < 0 || r > n - 1 || l > r)
{
Console.WriteLine("Invalid Input");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
static 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 max of values in this node
int mid = getMid(ss, se);
st[si] = Math.Max(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.
*/
static int[] constructST(int[] arr, int n)
{
// 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;
// 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 Code
static public void Main ()
{
int[] arr = { 1, 3, 5, 7, 9, 11 };
int n = arr.Length;
// Build segment tree from given array
int[] st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
Console.WriteLine("Max of values in given range = "
+ getMax(st, n, 1, 3));
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 1, 8, 0);
// Find max after the value is updated
Console.WriteLine("Updated max of values in given range = "
+ getMax(st, n, 1, 3));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript code for range maximum query and updates
// A utility function to get the
// middle index of given range.
function getMid(s,e)
{
return Math.floor(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
* node -> Index of current node in
* the segment tree.
* ss & se -> Starting and ending indexes
* of the segment represented
* by current node, i.e., st[node]
* l & r -> Starting and ending indexes
* of range query
*/
function MaxUtil(st,ss,se,l,r,node)
{
// If segment of this node is completely
// part of given range, then return
// the max of segment
if (l <= ss && r >= se)
return st[node];
// If segment of this node does not
// belong to given range
if (se < l || ss > r)
return -1;
// If segment of this node is partially
// the part of given range
let mid = getMid(ss, se);
return Math.max(
MaxUtil(st, ss, mid, l, r,
2 * node + 1),
MaxUtil(st, mid + 1, se, l, r,
2 * node + 2));
}
/*
* A recursive function to update the
nodes which have the given index in their
* range. The following are parameters
st, ss and se are same as defined above
* index -> index of the element to be updated.
*/
function updateValue(arr,st,ss,se,index,value,node)
{
if (index < ss || index > se) {
document.write("Invalid Input<br>");
return;
}
if (ss == se) {
// update value in array and in
// segment tree
arr[index] = value;
st[node] = value;
}
else {
let mid = getMid(ss, se);
if (index >= ss && index <= mid)
updateValue(arr, st, ss, mid,
index, value,
2 * node + 1);
else
updateValue(arr, st, mid + 1, se, index,
value, 2 * node + 2);
st[node] = Math.max(st[2 * node + 1],
st[2 * node + 2]);
}
return;
}
// Return max of elements in range from
// index l (query start) to r (query end).
function getMax(st,n,l,r)
{
// Check for erroneous input values
if (l < 0 || r > n - 1 || l > r) {
document.write("Invalid Input<br>");
return -1;
}
return MaxUtil(st, 0, n - 1, l, r, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
function 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 max of values in this node
let mid = getMid(ss, se);
st[si] = Math.max(
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.
*/
function constructST(arr,n)
{
// Height of segment tree
let x = Math.floor(Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
let max_size = 2 * Math.floor(Math.pow(2, x)) - 1;
// Allocate memory
let st = new Array(max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver Code
let arr=[ 1, 3, 5, 7, 9, 11];
let n = arr.length;
// Build segment tree from given array
let st = constructST(arr, n);
// Print max of values in array
// from index 1 to 3
document.write("Max of values in given range = "
+ getMax(st, n, 1, 3)+"<br>");
// Update: set arr[1] = 8 and update
// corresponding segment tree nodes.
updateValue(arr, st, 0, n - 1, 1, 8, 0);
// Find max after the value is updated
document.write(
"Updated max of values in given range = "
+ getMax(st, n, 1, 3)+"<br>");
// This code is contributed by patel2127
</script>
Producción
Max of values in given range = 7 Updated max of values in given range = 8
Publicación traducida automáticamente
Artículo escrito por Aman Goyal 2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA