Dada una array de N enteros positivos. La tarea es realizar las siguientes operaciones según el tipo de consulta dada.
1. Imprime el par máximo de productos en un rango dado. [LR]
2. Actualizar A i con algún valor dado.
Ejemplos:
Entrada: A={1, 3, 4, 2, 5}
Consultas:
Tipo 1: L = 0, R = 2.
Tipo 2: i = 1, val = 6
Tipo 1: L = 0, R = 2.
Salida :
12
24
Para la consulta 1, el producto máximo en un rango [0, 2] es 3*4 = 12.
Para la consulta 2, después de una actualización, la array se convierte en [1, 6, 4, 2, 5]
Para la consulta 3 , el producto máximo en un rango [0, 2] es 6*4 = 24.
Solución ingenua : el enfoque de fuerza bruta es atravesar de L a R y verificar cada par y luego encontrar el par de productos máximo entre ellos.
Complejidad de tiempo : O (N ^ 2) para cada consulta.
Una mejor solución es encontrar el primer y el segundo número más grande en el rango de L a R recorriendo y luego devolviendo su producto.
Complejidad de tiempo : O(N) para cada consulta.
Una solución eficiente es utilizar un árbol de segmentos para almacenar el mayor y el segundo mayor número en los Nodes y luego devolver el producto de ellos.
A continuación se muestra la implementación del enfoque anterior.
CPP
// C++ program to find the maximum
// product in a range with updates
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// structure defined
struct segment {
// l for largest
// sl for second largest
ll l;
ll sl;
};
// function to perform queries
segment query(segment* tree, ll index,
ll s, ll e, ll qs, ll qe)
{
segment res;
res.l = -1;
res.sl = -1;
// no overlapping case
if (qs > e || qe < s || s > e) {
return res;
}
// complete overlap case
if (s >= qs && e <= qe) {
return tree[index];
}
// partial overlap case
ll mid = (s + e) / 2;
// calling left node and right node
segment left = query(tree, 2 * index,
s, mid, qs, qe);
segment right = query(tree, 2 * index + 1,
mid + 1, e, qs, qe);
// largest of ( left.l, right.l)
ll largest = max(left.l, right.l);
// compute second largest
// second largest will be minimum
// of maximum from left and right node
ll second_largest = min(max(left.l, right.sl),
max(right.l, left.sl));
// store largest and
// second_largest in res
res.l = largest;
res.sl = second_largest;
// return the resulting node
return res;
}
// function to update the query
void update(segment* tree, ll index,
ll s, ll e, ll i, ll val)
{
// no overlapping case
if (i < s || i > e) {
return;
}
// reached leaf node
if (s == e) {
tree[index].l = val;
tree[index].sl = INT_MIN;
return;
}
// partial overlap
ll mid = (s + e) / 2;
// left subtree call
update(tree, 2 * index, s, mid, i, val);
// right subtree call
update(tree, 2 * index + 1, mid + 1, e, i, val);
// largest of ( left.l, right.l)
tree[index].l = max(tree[2 * index].l, tree[2 * index + 1].l);
// compute second largest
// second largest will be
// minimum of maximum from left and right node
tree[index].sl = min(max(tree[2 * index].l, tree[2 * index + 1].sl),
max(tree[2 * index + 1].l, tree[2 * index].sl));
}
// Function to build the tree
void buildtree(segment* tree, ll* a, ll index, ll s, ll e)
{
// tree is build bottom to up
if (s > e) {
return;
}
// leaf node
if (s == e) {
tree[index].l = a[s];
tree[index].sl = INT_MIN;
return;
}
ll mid = (s + e) / 2;
// calling the left node
buildtree(tree, a, 2 * index, s, mid);
// calling the right node
buildtree(tree, a, 2 * index + 1, mid + 1, e);
// largest of ( left.l, right.l)
ll largest = max(tree[2 * index].l, tree[2 * index + 1].l);
// compute second largest
// second largest will be minimum
// of maximum from left and right node
ll second_largest = min(max(tree[2 * index].l, tree[2 * index + 1].sl),
max(tree[2 * index + 1].l, tree[2 * index].sl));
// storing the largest and
// second_largest values in the current node
tree[index].l = largest;
tree[index].sl = second_largest;
}
// Driver Code
int main()
{
// your code goes here
ll n = 5;
ll a[5] = { 1, 3, 4, 2, 5 };
// allocating memory for segment tree
segment* tree = new segment[4 * n + 1];
// buildtree(tree, a, index, start, end)
buildtree(tree, a, 1, 0, n - 1);
// query section
// storing the resulting node
segment res = query(tree, 1, 0, n - 1, 0, 2);
cout << "Maximum product in the range "
<< "0 and 2 before update: " << (res.l * res.sl);
// update section
// update(tree, index, start, end, i, v)
update(tree, 1, 0, n - 1, 1, 6);
res = query(tree, 1, 0, n - 1, 0, 2);
cout << "\nMaximum product in the range "
<< "0 and 2 after update: " << (res.l * res.sl);
return 0;
}
Maximum product in the range 0 and 2 before update: 12 Maximum product in the range 0 and 2 after update: 24
Complejidad de tiempo : O (log N) por consulta y O (N) para construir el árbol.
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA