Dado un número N, y Q consultas de dos tipos 1 y 2. La tarea es escribir un código para la consulta dada donde, en el tipo 1, dados l y r, y la tarea es imprimir la suma más grande del subarreglo contiguo y para el tipo 2, dado el tipo, el índice y el valor, actualice el valor a A index .
Ejemplos:
Input : a = {-2, -3, 4, -1, -2, 1, 5, -3}
1st query : 1 5 8
2nd query : 2 1 10
3rd query : 1 1 3
Output : Answer to 1st query : 6
Answer to 3rd query : 11
Explicación: en la primera consulta, la tarea es imprimir la suma más grande de un subarreglo contiguo en el rango 5-8, que consta de {-2, 1, 5, -3}. La suma mayor es 6, que está formada por el subarreglo {1, 5}. En la segunda consulta, se realiza una operación de actualización, que actualiza a[1] a 10, por lo que la secuencia es {10, -3, 4, -1, -2, 1, 5, -3}. En la tercera consulta, la tarea es imprimir la suma más grande de un subarreglo contiguo en el rango 1-3, que consta de {10, -3, 4}. La suma mayor es 11, que está formada por el subarreglo {10, -3, 4}.
Un enfoque ingenuo es usar el algoritmo de Kadane para cada consulta de tipo 1. La complejidad de cada consulta de tipo 1 es O(n). La consulta de tipo 2 se realiza en O(1).
Enfoque eficiente:
un enfoque eficiente es crear un árbol de segmentos en el que cada Node almacene cuatro valores (sum, prefixsum, suffixsum, maxsum) y realizar una consulta de rango para encontrar la respuesta a cada consulta. Los Nodes del árbol de segmentos almacenan los cuatro valores mencionados anteriormente. El padre almacenará la fusión del hijo izquierdo y derecho. El Node principal almacena el valor como se menciona a continuación:
padre.suma = izquierda.suma + derecha.suma
padre.prefijosum = max(izquierda.prefijosum, izquierda.suma + derecha.prefijosum)
padre.sumasufijo = max(derecha.sumasufijo, derecha.suma + izquierda.sumasufijo)
padre.sumamáxima = max(padre.sumaprefijo, padre.sumasufijo, izquierda.sumamáxima, derecha.sumamáxima, izquierda.sumasufijo + derecha.sumaprefijo)
El Node principal almacena lo siguiente:
- La suma del Node padre es la suma de la suma del hijo izquierdo y derecho.
- La suma del prefijo del Node padre será equivalente al máximo de la suma del prefijo del hijo izquierdo o la suma del hijo izquierdo + la suma del prefijo del hijo derecho.
- La suma del sufijo del Node padre será igual a la suma del sufijo del hijo derecho o la suma del sufijo del hijo derecho + la suma del sufijo del hijo izquierdo
- La suma máxima del Node padre será el máximo de la suma de prefijos o la suma de sufijos del padre o la suma máxima del hijo izquierdo o derecho o la suma de la suma de sufijos del hijo izquierdo y la suma de prefijos del hijo derecho.
Representación de árboles de segmentos:
1. Los Nodes hoja son los elementos de la array de entrada.
2. Cada Node interno representa alguna fusión de los Nodes hoja. La fusión puede ser diferente para diferentes problemas. Para este problema, la fusión se realiza como se indicó anteriormente.
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 2 * i + 2 y el padre está en (i – 1)/2 .
Construcción del árbol de segmentos a partir de una array dada:
Comience con un segmento arr[0 . . . n-1]. y cada vez divida el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llame al mismo procedimiento en ambas mitades, y para cada segmento, almacene los valores en las cuatro variables como se indica en las fórmulas anteriores.
Actualice un valor dado en la array y el segmento Tree:
comience con el segmento completo de la array que se nos proporcionó. Cada vez que divida la array en dos mitades, ignore la mitad en la que no está presente el índice que se va a actualizar . Siga ignorando las mitades en cada paso hasta llegar al Node hoja, donde actualice el valor al índice dado. Ahora, combine los valores actualizados de acuerdo con las fórmulas dadas para todos los Nodes que están presentes en el camino que hemos recorrido.
Responder a una consulta:
para cada consulta, muévase a las mitades izquierda y derecha del árbol. Siempre que el rango dado se superponga por completo a cualquier mitad de un árbol, devuelva el Node de esa mitad sin atravesar más esa región. Cuando una mitad del árbol se encuentra completamente fuera del rango dado, devuelve INT_MIN. En la superposición parcial del rango, atraviese en mitades izquierda y derecha y regrese en consecuencia.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find Largest Sum Contiguous
// Subarray in a given range with updates
#include <bits/stdc++.h>
using namespace std;
// Structure to store
// 4 values that are to be stored
// in the nodes
struct node {
int sum, prefixsum, suffixsum, maxsum;
};
// array to store the segment tree
node tree[4 * 100];
// function to build the tree
void build(int arr[], int low, int high, int index)
{
// the leaf node
if (low == high) {
tree[index].sum = arr[low];
tree[index].prefixsum = arr[low];
tree[index].suffixsum = arr[low];
tree[index].maxsum = arr[low];
}
else {
int mid = (low + high) / 2;
// left subtree
build(arr, low, mid, 2 * index + 1);
// right subtree
build(arr, mid + 1, high, 2 * index + 2);
// parent node's sum is the summation
// of left and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum =
max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum =
max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and right
// child's prefix.
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2 * index + 1].maxsum,
max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// function to update the tree
void update(int arr[], int index, int low, int high,
int idx, int value)
{
// the node to be updated
if (low == high) {
tree[index].sum = value;
tree[index].prefixsum = value;
tree[index].suffixsum = value;
tree[index].maxsum = value;
}
else {
int mid = (low + high) / 2;
// if node to be updated is in left subtree
if (idx <= mid)
update(arr, 2 * index + 1, low, mid, idx, value);
// if node to be updated is in right subtree
else
update(arr, 2 * index + 2, mid + 1,
high, idx, value);
// parent node's sum is the summation of left
// and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum =
max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum =
max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and
// right child's prefix.
tree[index].maxsum =
max(tree[index].prefixsum,
max(tree[index].suffixsum,
max(tree[2 * index + 1].maxsum,
max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// function to return answer to every type-1 query
node query(int arr[], int index, int low,
int high, int l, int r)
{
// initially all the values are INT_MIN
node result;
result.sum = result.prefixsum =
result.suffixsum =
result.maxsum = INT_MIN;
// range does not lies in this subtree
if (r < low || high < l)
return result;
// complete overlap of range
if (l <= low && high <= r)
return tree[index];
int mid = (low + high) / 2;
// right subtree
if (l > mid)
return query(arr, 2 * index + 2,
mid + 1, high, l, r);
// left subtree
if (r <= mid)
return query(arr, 2 * index + 1,
low, mid, l, r);
node left = query(arr, 2 * index + 1,
low, mid, l, r);
node right = query(arr, 2 * index + 2,
mid + 1, high, l, r);
// finding the maximum and returning it
result.sum = left.sum + right.sum;
result.prefixsum = max(left.prefixsum, left.sum +
right.prefixsum);
result.suffixsum = max(right.suffixsum,
right.sum + left.suffixsum);
result.maxsum = max(result.prefixsum,
max(result.suffixsum,
max(left.maxsum,
max(right.maxsum,
left.suffixsum + right.prefixsum))));
return result;
}
// Driver Code
int main()
{
int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = sizeof(a) / sizeof(a[0]);
// build the tree
build(a, 0, n - 1, 0);
// 1st query type-1
int l = 5, r = 8;
cout << query(a, 0, 0, n - 1, l - 1, r - 1).maxsum;
cout << endl;
// 2nd type-2 query
int index = 1;
int value = 10;
a[index - 1] = value;
update(a, 0, 0, n - 1, index - 1, value);
// 3rd type-1 query
l = 1, r = 3;
cout << query(a, 0, 0, n - 1, l - 1, r - 1).maxsum;
return 0;
}
Java
// Java program to find Largest Sum Contiguous
// Subarray in a given range with updates
class GFG
{
// Structure to store 4 values that are
// to be stored in the nodes
static class node
{
int sum, prefixsum, suffixsum, maxsum;
};
// array to store the segment tree
static node[] tree = new node[4 * 100];
// function to build the tree
static void build(int arr[], int low,
int high, int index)
{
// the leaf node
if (low == high)
{
tree[index].sum = arr[low];
tree[index].prefixsum = arr[low];
tree[index].suffixsum = arr[low];
tree[index].maxsum = arr[low];
}
else
{
int mid = (low + high) / 2;
// left subtree
build(arr, low, mid, 2 * index + 1);
// right subtree
build(arr, mid + 1, high, 2 * index + 2);
// parent node's sum is the summation
// of left and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum = Math.max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum = Math.max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and right
// child's prefix.
tree[index].maxsum = Math.max(tree[index].prefixsum,
Math.max(tree[index].suffixsum,
Math.max(tree[2 * index + 1].maxsum,
Math.max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// function to update the tree
static void update(int arr[], int index, int low,
int high, int idx, int value)
{
// the node to be updated
if (low == high)
{
tree[index].sum = value;
tree[index].prefixsum = value;
tree[index].suffixsum = value;
tree[index].maxsum = value;
}
else
{
int mid = (low + high) / 2;
// if node to be updated is in left subtree
if (idx <= mid)
{
update(arr, 2 * index + 1, low,
mid, idx, value);
}
// if node to be updated is in right subtree
else
{
update(arr, 2 * index + 2, mid + 1,
high, idx, value);
}
// parent node's sum is the summation of left
// and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum = Math.max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum = Math.max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and
// right child's prefix.
tree[index].maxsum = Math.max(tree[index].prefixsum,
Math.max(tree[index].suffixsum,
Math.max(tree[2 * index + 1].maxsum,
Math.max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// function to return answer to every type-1 query
static node query(int arr[], int index,
int low, int high, int l, int r)
{
// initially all the values are Integer.MIN_VALUE
node result = new node();
result.sum = result.prefixsum
= result.suffixsum
= result.maxsum = Integer.MIN_VALUE;
// range does not lies in this subtree
if (r < low || high < l)
{
return result;
}
// complete overlap of range
if (l <= low && high <= r)
{
return tree[index];
}
int mid = (low + high) / 2;
// right subtree
if (l > mid)
{
return query(arr, 2 * index + 2,
mid + 1, high, l, r);
}
// left subtree
if (r <= mid)
{
return query(arr, 2 * index + 1,
low, mid, l, r);
}
node left = query(arr, 2 * index + 1,
low, mid, l, r);
node right = query(arr, 2 * index + 2,
mid + 1, high, l, r);
// finding the maximum and returning it
result.sum = left.sum + right.sum;
result.prefixsum = Math.max(left.prefixsum,
left.sum + right.prefixsum);
result.suffixsum = Math.max(right.suffixsum,
right.sum + left.suffixsum);
result.maxsum = Math.max(result.prefixsum,
Math.max(result.suffixsum,
Math.max(left.maxsum,
Math.max(right.maxsum, left.suffixsum +
right.prefixsum))));
return result;
}
// Driver Code
public static void main(String[] args)
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = a.length;
for (int i = 0; i < 4 * 100; i++)
{
tree[i] = new node();
}
// build the tree
build(a, 0, n - 1, 0);
// 1st query type-1
int l = 5, r = 8;
System.out.print(query(a, 0, 0, n - 1,
l - 1, r - 1).maxsum);
System.out.println();
// 2nd type-2 query
int index = 1;
int value = 10;
a[index - 1] = value;
update(a, 0, 0, n - 1, index - 1, value);
// 3rd type-1 query
l = 1;
r = 3;
System.out.print(query(a, 0, 0, n - 1,
l - 1, r - 1).maxsum);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to find Largest Sum Contiguous # Subarray in a given range with updates from sys import maxsize INT_MIN = -maxsize # Structure to store # 4 values that are to be stored # in the nodes class node: def __init__(self): self.sum = 0 self.prefixsum = 0 self.suffixsum = 0 self.maxsum = 0 # array to store the segment tree tree = [0] * (4 * 100) for i in range(4 * 100): tree[i] = node() def build(arr: list, low: int, high: int, index: int): global tree # the leaf node if low == high: tree[index].sum = arr[low] tree[index].prefixsum = arr[low] tree[index].suffixsum = arr[low] tree[index].maxsum = arr[low] else: mid = (low + high) >> 1 # left subtree build(arr, low, mid, 2 * index + 1) # right subtree build(arr, mid + 1, high, 2 * index + 2) # parent node's sum is the summation # of left and right child tree[index].sum = tree[2 * index + 1].sum + \ tree[2 * index + 2].sum # parent node's prefix sum will be equivalent # to maximum of left child's prefix sum or left # child sum + right child prefix sum. tree[index].prefixsum = max( tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum) # parent node's suffix sum will be equal to right # child suffix sum or right child sum + suffix # sum of left child tree[index].suffixsum = max( tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum) # maximum will be the maximum of prefix, suffix of # parent or maximum of left child or right child # and summation of left child's suffix and right # child's prefix. tree[index].maxsum = max(tree[index].prefixsum, max(tree[index].suffixsum, max(tree[2 * index + 1].maxsum, max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2].prefixsum)))) # function to update the tree def update(arr: list, index: int, low: int, high: int, idx: int, value: int): global tree # the node to be updated if low == high: tree[index].sum = value tree[index].prefixsum = value tree[index].suffixsum = value tree[index].maxsum = value else: mid = (low + high) >> 1 # if node to be updated is in left subtree if idx <= mid: update(arr, 2 * index + 1, low, mid, idx, value) # if node to be updated is in right subtree else: update(arr, 2 * index + 2, mid + 1, high, idx, value) # parent node's sum is the summation of left # and right child tree[index].sum = tree[2 * index + 1].sum + \ tree[2 * index + 2].sum # parent node's prefix sum will be equivalent # to maximum of left child's prefix sum or left # child sum + right child prefix sum. tree[index].prefixsum = max(tree[2 * index + 1].prefixsum, tree[2 * index + 1].sum + tree[2 * index + 2].prefixsum) # parent node's suffix sum will be equal to right # child suffix sum or right child sum + suffix # sum of left child tree[index].suffixsum = max(tree[2 * index + 2].suffixsum, tree[2 * index + 2].sum + tree[2 * index + 1].suffixsum) # maximum will be the maximum of prefix, suffix of # parent or maximum of left child or right child # and summation of left child's suffix and # right child's prefix. tree[index].maxsum = max(tree[index].prefixsum, max(tree[index].suffixsum, max(tree[2 * index + 1].maxsum, max(tree[2 * index + 2].maxsum, tree[2 * index + 1].suffixsum + tree[2 * index + 2].prefixsum)))) # function to return answer to every type-1 query def query(arr: list, index: int, low: int, high: int, l: int, r: int) -> node: # initially all the values are INT_MIN result = node() result.sum = result.prefixsum = result.\ suffixsum = result.maxsum = INT_MIN # range does not lies in this subtree if r < low or high < l: return result # complete overlap of range if l <= low and high <= r: return tree[index] mid = (low + high) >> 1 # right subtree if l > mid: return query(arr, 2 * index + 2, mid + 1, high, l, r) # left subtree if r <= mid: return query(arr, 2 * index + 1, low, mid, l, r) left = query(arr, 2 * index + 1, low, mid, l, r) right = query(arr, 2 * index + 2, mid + 1, high, l, r) # finding the maximum and returning it result.sum = left.sum + right.sum result.prefixsum = max(left.prefixsum, left.sum + right.prefixsum) result.suffixsum = max(right.suffixsum, right.sum + left.suffixsum) result.maxsum = max(result.prefixsum, max(result.suffixsum, max(left.maxsum, max(right.maxsum, left.suffixsum + right.prefixsum)))) return result # Driver Code if __name__ == "__main__": a = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(a) # build the tree build(a, 0, n - 1, 0) # 1st query type-1 l = 5 r = 8 print(query(a, 0, 0, n - 1, l - 1, r - 1).maxsum) # 2nd type-2 query index = 1 value = 10 a[index - 1] = value update(a, 0, 0, n - 1, index - 1, value) # 3rd type-1 query l = 1 r = 3 print(query(a, 0, 0, n - 1, l - 1, r - 1).maxsum) # This code is contributed by # sanjeev2552
C#
// C# program to find Largest Sum Contiguous
// Subarray in a given range with updates
using System;
using System.Collections.Generic;
class GFG
{
// Structure to store 4 values that are
// to be stored in the nodes
public class node
{
public int sum, prefixsum, suffixsum, maxsum;
};
// array to store the segment tree
static node[] tree = new node[4 * 100];
// function to build the tree
static void build(int []arr, int low,
int high, int index)
{
// the leaf node
if (low == high)
{
tree[index].sum = arr[low];
tree[index].prefixsum = arr[low];
tree[index].suffixsum = arr[low];
tree[index].maxsum = arr[low];
}
else
{
int mid = (low + high) / 2;
// left subtree
build(arr, low, mid, 2 * index + 1);
// right subtree
build(arr, mid + 1, high, 2 * index + 2);
// parent node's sum is the summation
// of left and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum = Math.Max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum = Math.Max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and right
// child's prefix.
tree[index].maxsum = Math.Max(tree[index].prefixsum,
Math.Max(tree[index].suffixsum,
Math.Max(tree[2 * index + 1].maxsum,
Math.Max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// function to update the tree
static void update(int []arr, int index, int low,
int high, int idx, int value)
{
// the node to be updated
if (low == high)
{
tree[index].sum = value;
tree[index].prefixsum = value;
tree[index].suffixsum = value;
tree[index].maxsum = value;
}
else
{
int mid = (low + high) / 2;
// if node to be updated is in left subtree
if (idx <= mid)
{
update(arr, 2 * index + 1, low,
mid, idx, value);
}
// if node to be updated is in right subtree
else
{
update(arr, 2 * index + 2, mid + 1,
high, idx, value);
}
// parent node's sum is the summation of left
// and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum = Math.Max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum = Math.Max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and
// right child's prefix.
tree[index].maxsum = Math.Max(tree[index].prefixsum,
Math.Max(tree[index].suffixsum,
Math.Max(tree[2 * index + 1].maxsum,
Math.Max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// function to return answer to every type-1 query
static node query(int []arr, int index,
int low, int high, int l, int r)
{
// initially all the values are int.MinValue
node result = new node();
result.sum = result.prefixsum
= result.suffixsum
= result.maxsum = int.MinValue;
// range does not lies in this subtree
if (r < low || high < l)
{
return result;
}
// complete overlap of range
if (l <= low && high <= r)
{
return tree[index];
}
int mid = (low + high) / 2;
// right subtree
if (l > mid)
{
return query(arr, 2 * index + 2,
mid + 1, high, l, r);
}
// left subtree
if (r <= mid)
{
return query(arr, 2 * index + 1,
low, mid, l, r);
}
node left = query(arr, 2 * index + 1,
low, mid, l, r);
node right = query(arr, 2 * index + 2,
mid + 1, high, l, r);
// finding the maximum and returning it
result.sum = left.sum + right.sum;
result.prefixsum = Math.Max(left.prefixsum,
left.sum + right.prefixsum);
result.suffixsum = Math.Max(right.suffixsum,
right.sum + left.suffixsum);
result.maxsum = Math.Max(result.prefixsum,
Math.Max(result.suffixsum,
Math.Max(left.maxsum,
Math.Max(right.maxsum, left.suffixsum +
right.prefixsum))));
return result;
}
// Driver Code
public static void Main(String[] args)
{
int []a = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = a.Length;
for (int i = 0; i < 4 * 100; i++)
{
tree[i] = new node();
}
// build the tree
build(a, 0, n - 1, 0);
// 1st query type-1
int l = 5, r = 8;
Console.Write(query(a, 0, 0, n - 1,
l - 1, r - 1).maxsum);
Console.WriteLine();
// 2nd type-2 query
int index = 1;
int value = 10;
a[index - 1] = value;
update(a, 0, 0, n - 1, index - 1, value);
// 3rd type-1 query
l = 1;
r = 3;
Console.Write(query(a, 0, 0, n - 1,
l - 1, r - 1).maxsum);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find Largest Sum
// Contiguous Subarray in a given range
// with updates
// Structure to store 4 values that are
// to be stored in the nodes
class node
{
constructor()
{
this.sum = 0;
this.prefixsum = 0;
this.suffixsum = 0;
this.maxsum = 0;
}
};
// Array to store the segment tree
var tree = Array(4 * 100).fill(new node());
// Function to build the tree
function build(arr, low, high, index)
{
// The leaf node
if (low == high)
{
tree[index].sum = arr[low];
tree[index].prefixsum = arr[low];
tree[index].suffixsum = arr[low];
tree[index].maxsum = arr[low];
}
else
{
var mid = parseInt((low + high) / 2);
// Left subtree
build(arr, low, mid, 2 * index + 1);
// Right subtree
build(arr, mid + 1, high, 2 * index + 2);
// Parent node's sum is the summation
// of left and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// Parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum = Math.max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// Parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum = Math.max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and right
// child's prefix.
tree[index].maxsum = Math.max(tree[index].prefixsum,
Math.max(tree[index].suffixsum,
Math.max(tree[2 * index + 1].maxsum,
Math.max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// Function to update the tree
function update(arr, index, low, high, idx, value)
{
// The node to be updated
if (low == high)
{
tree[index].sum = value;
tree[index].prefixsum = value;
tree[index].suffixsum = value;
tree[index].maxsum = value;
}
else
{
var mid = parseInt((low + high) / 2);
// If node to be updated is in left subtree
if (idx <= mid)
{
update(arr, 2 * index + 1, low,
mid, idx, value);
}
// If node to be updated is in right subtree
else
{
update(arr, 2 * index + 2, mid + 1,
high, idx, value);
}
// Parent node's sum is the summation of left
// and right child
tree[index].sum = tree[2 * index + 1].sum +
tree[2 * index + 2].sum;
// Parent node's prefix sum will be equivalent
// to maximum of left child's prefix sum or left
// child sum + right child prefix sum.
tree[index].prefixsum = Math.max(tree[2 * index + 1].prefixsum,
tree[2 * index + 1].sum +
tree[2 * index + 2].prefixsum);
// Parent node's suffix sum will be equal to right
// child suffix sum or right child sum + suffix
// sum of left child
tree[index].suffixsum = Math.max(tree[2 * index + 2].suffixsum,
tree[2 * index + 2].sum +
tree[2 * index + 1].suffixsum);
// maximum will be the maximum of prefix, suffix of
// parent or maximum of left child or right child
// and summation of left child's suffix and
// right child's prefix.
tree[index].maxsum = Math.max(tree[index].prefixsum,
Math.max(tree[index].suffixsum,
Math.max(tree[2 * index + 1].maxsum,
Math.max(tree[2 * index + 2].maxsum,
tree[2 * index + 1].suffixsum +
tree[2 * index + 2].prefixsum))));
}
}
// Function to return answer to every type-1 query
function query(arr, index, low, high, l, r)
{
// Initially all the values are int.MinValue
var result = new node();
result.sum = result.prefixsum = result.suffixsum =
result.maxsum = -1000000000;
// Range does not lies in this subtree
if (r < low || high < l)
{
return result;
}
// Complete overlap of range
if (l <= low && high <= r)
{
return tree[index];
}
var mid = parseInt((low + high) / 2);
// Right subtree
if (l > mid)
{
return query(arr, 2 * index + 2,
mid + 1, high, l, r);
}
// Left subtree
if (r <= mid)
{
return query(arr, 2 * index + 1,
low, mid, l, r);
}
var left = query(arr, 2 * index + 1,
low, mid, l, r);
var right = query(arr, 2 * index + 2,
mid + 1, high, l, r);
// Finding the maximum and returning it
result.sum = left.sum + right.sum;
result.prefixsum = Math.max(left.prefixsum,
left.sum + right.prefixsum);
result.suffixsum = Math.max(right.suffixsum,
right.sum + left.suffixsum);
result.maxsum = Math.max(result.prefixsum,
Math.max(result.suffixsum,
Math.max(left.maxsum,
Math.max(right.maxsum, left.suffixsum +
right.prefixsum))));
return result;
}
// Driver Code
var a = [ -2, -3, 4, -1, -2, 1, 5, -3 ];
var n = a.length;
for(var i = 0; i < 4 * 100; i++)
{
tree[i] = new node();
}
// Build the tree
build(a, 0, n - 1, 0);
// 1st query type-1
var l = 5, r = 8;
document.write(query(a, 0, 0, n - 1,
l - 1, r - 1).maxsum);
document.write("<br>");
// 2nd type-2 query
var index = 1;
var value = 10;
a[index - 1] = value;
update(a, 0, 0, n - 1, index - 1, value);
// 3rd type-1 query
l = 1;
r = 3;
document.write(query(a, 0, 0, n - 1,
l - 1, r - 1).maxsum);
// This code is contributed by rrrtnx
</script>
Producción:
6 11
Complejidad de tiempo: O (n log n) para construir el árbol, O (log n) para cada consulta de tipo 1, O (1) para consulta de tipo 2.
Tema relacionado: Árbol de segmentos