Suma y máximo de elementos en la array de [L, R] antes y después de las actualizaciones

Posted on by Rudeus Greyrat

Requisito previo: Árboles de segmento , Propagación diferida en árbol de segmento .
Dada una array arr[] de N enteros. La tarea es hacer las siguientes operaciones:

  1. Cambie el valor arr[i] a min(arr[i], X) donde X es un número entero para un rango dado [L, R] .
  2. Encuentre el valor máximo del índice L a R donde 0 ≤ L ≤ R ≤ N-1 antes y después de la actualización dada a la array anterior.
  3. Encuentre la suma del elemento del índice L a R donde 0 ≤ L ≤ R ≤ N-1 antes y después de la actualización dada a la array anterior.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}, L = 2, R = 4, X = 3 Salida:
Máximo
en el rango [2, 4] antes de la actualización: 5
Suma en el rango [2, 4 ] antes de la actualización: 12
Máximo en el rango [2, 4] después de la actualización: 3
Suma en el rango [2, 4] después de la actualización: 9
Explicación:
Antes de la actualización:
arr[] = {1, 2, 3, 4, 5}
El el valor máximo de [L, R] es 5
La suma en el rango [L, R] es 3 + 4 + 5 = 12

Después de la actualización:
arr[] = {1, 2, 3, 3, 3}
El valor máximo de [L, R] es 3
La suma en el rango [L, R] es 3 + 3 + 3 = 9

Entrada: arr[] = {1, 4, 19, 0, 7, 22, 7}, L = 1, R = 5, X = 14 Salida: Máximo en el
rango
[1, 5] antes de la actualización: 22
Suma en el rango [1, 5] antes de la actualización: 52
Máximo en el rango [1, 5] después de la actualización: 22
Suma en el rango [1, 5] después de la actualización: 39
Explicación:
Antes de la actualización:
arr[] = {1, 4, 19, 0 , 7, 22, 7}
El valor máximo de [L, R] es 22
La suma en el rango [L, R] es 4 + 19 + 0 + 7 + 22 = 52

Después de la actualización:
arr[] = {1, 4, 14, 0, 7, 14, 7}
El valor máximo de [L, R] es 14 La
suma en el rango [L, R] es 4 + 14 + 0 + 7 + 14 = 39

Enfoque:
algunos términos para la propagación perezosa :

  1. pushdown(): la etiqueta perezosa se aplica al Node actual y luego se empuja hacia abajo a sus hijos.
  2. tag_condition: es la condición que debe cumplirse para establecer el Node perezoso. En los árboles perezosos normales, generalmente la condición es que los rangos de las cubiertas de los Nodes se encuentran completamente en el rango de actualización.
  3. Un Node en el árbol de segmentos representa un rango de la array. Ahora todos los elementos en ese rango tendrán diferentes valores y cambiarán en diferentes cantidades durante una actualización. Entonces necesitamos la información sobre valores distintos y sus conteos en ese rango. Entonces, esto se convierte en una operación O (N) en el peor de los casos, ya que en un máximo de N Nodes distintos en un rango.
  4. A continuación se muestra el enfoque para resolver estas restricciones en Segment Tree . Cada Node en el Árbol de Segmentos tendrá los siguientes valores:
    • valor : el valor de un rango, aquí la suma de todos los elementos en ese rango
    • maxval : valor máximo en ese rango
    • secondmax : segundo valor máximo estricto en ese rango
    • cnt_max : Recuento del valor máximo en ese rango
    • cnt_secondmax : Recuento de secondmax en ese rango

A continuación se muestran los pasos:

  1. Forme un árbol de segmentos para el elemento de array dado con todos los Nodes que tengan las propiedades mencionadas anteriormente.
  2. Para la llamada updateQuery() , haga lo siguiente:
    • Si max_value es menor que el valor actualizado (por ejemplo, X ), entonces no se cambiará ningún valor ya que min(arr[i], X) será arr[i] en este caso.
    • Si secondmax ≤ X ≤ maxvalue , actualice el valor de ese Node y newSum se calculará mediante: 
      new_sum = sum - f*maxvalue + f*X, 
where f is the frequency of maxvalue
  3. Consulta para encontrar el número máximo en el rango [L, R] :
    • Si el rango [L, R] se encuentra completamente fuera del rango, devuelva 0 .
    • Si el rango [L, R] se encuentra completamente dentro del rango, entonces el valor máximo para el rango actual es tree[pos].mx1 .
    • De lo contrario, verifique la condición anterior para el subárbol izquierdo y derecho recursivamente.
    • El valor máximo para todas las llamadas recursivas anteriores da el valor máximo en el rango [L, R] .
  4. Consulta para encontrar la suma en el rango [L, R] :
    • Si el rango [L, R] se encuentra completamente fuera del rango, devuelva 0.
    • Si el rango [L, R] se encuentra completamente dentro del rango, entonces la suma del rango actual es tree[pos].sum .
    • De lo contrario, verifique la condición anterior para el subárbol izquierdo y derecho recursivamente.
    • La suma de todos los valores para la llamada recursiva anterior da la suma en el rango [L, R] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Node for each Segment Tree
typedef struct node {
  
    int sum;
    int mx1;
    int mx2;
    int cnt_mx1;
    int cnt_mx2;
  
    // Constructor
    node()
    {
        sum = mx1 = mx2 = 0;
        cnt_mx1 = cnt_mx2 = 0;
    }
  
} node;
  
const int N = 1e5 + 5;
  
// Segment Tree Node
node tree[N];
  
// For Lazy Propagation
int lazy[N];
  
// Function to merge 2 nodes of Segment
// Tree
void combine(int pos)
{
  
    // Map to store the count of
    // maximum1 and maximum2 for every
    // node segment tree
    map<int, int> x;
  
    // Update the count for left and
    // right subtree
    x[tree[2 * pos + 1].mx1] += tree[2 * pos + 1].cnt_mx1;
    x[tree[2 * pos + 1].mx2] += tree[2 * pos + 1].cnt_mx2;
    x[tree[2 * pos + 2].mx1] += tree[2 * pos + 2].cnt_mx1;
    x[tree[2 * pos + 2].mx2] += tree[2 * pos + 2].cnt_mx2;
  
    // Vector pair to store mx1 & mx2
    vector<pair<int, int> > v;
  
    // Traverse the v
    for (auto it = x.begin(); it != x.end(); it++) {
        v.push_back({ it->first, it->second });
    }
  
    int n = v.size();
  
    // Update the mx1 and mx2 after
    // combined node
    tree[pos].mx1 = v[n - 1].first;
    tree[pos].cnt_mx1 = v[n - 1].second;
  
    // If only one node
    if (n == 1) {
        tree[pos].mx2 = tree[pos].cnt_mx2 = 0;
    }
  
    // ELse Update mx2 and cnt_mx2
    else {
        tree[pos].mx2 = v[n - 2].first;
        tree[pos].cnt_mx2 = v[n - 2].second;
    }
  
    // Update the sum
    tree[pos].sum = tree[2 * pos + 1].sum
                    + tree[2 * pos + 2].sum;
}
  
// Function that returns true if tag
// condition is satisfied, and we can
// do lazy update
bool tag_condition(int pos, int x)
{
    if (tree[pos].mx1 > x
        && tree[pos].mx2 <= x) {
        return true;
    }
    return false;
}
  
// Function that pushes down the lazy
// value of the current node to its children
void pushdown(int beg, int end, int pos)
{
    // If tag condition satisfies
    if (tag_condition(pos, lazy[pos])) {
  
        int initsum = tree[pos].mx1 * tree[pos].cnt_mx1;
        int finsum = lazy[pos] * tree[pos].cnt_mx1;
        tree[pos].sum += finsum - initsum;
  
        // If only one node, then update the
        // maximum value to current position
        if (beg == end)
            tree[pos].mx1 = lazy[pos];
  
        // If lazy[pos] > maximum value
        else {
  
            // Update mx1 to current
            // lazy[pos]
            if (lazy[pos] > tree[pos].mx2)
                tree[pos].mx1 = lazy[pos];
  
            // Else update the count
            else {
  
                tree[pos].mx1 = lazy[pos];
                tree[pos].cnt_mx1 += tree[pos].cnt_mx2;
                tree[pos].mx2 = tree[pos].cnt_mx2 = 0;
  
                // map to store the cnt
                // of maximum1 and maximum2
                // for every node in segment
                // tree
                map<int, int> x;
                x[tree[2 * pos + 1].mx1] += tree[2 * pos + 1].cnt_mx1;
                x[tree[2 * pos + 1].mx2] += tree[2 * pos + 1].cnt_mx2;
                x[tree[2 * pos + 2].mx1] += tree[2 * pos + 2].cnt_mx1;
                x[tree[2 * pos + 2].mx2] += tree[2 * pos + 2].cnt_mx2;
  
                // Traverse the map
                for (auto it = x.begin(); it != x.end(); it++) {
  
                    // Update the maximum
                    // count
                    if (it->first != tree[pos].mx1
                        && it->first > tree[pos].mx2) {
                        tree[pos].mx2 = it->first;
                        tree[pos].cnt_mx2 = it->second;
                    }
                }
            }
  
            // Update the value for
            // lazy left and right
            // subtree
            lazy[2 * pos + 1] = min(lazy[2 * pos + 1],
                                    lazy[pos]);
            lazy[2 * pos + 2] = min(lazy[2 * pos + 2],
                                    lazy[pos]);
        }
    }
  
    lazy[pos] = INT_MAX;
}
  
// Function that Lazy update in segment
// tree i.e., arr[i] = min(arr[i], val)
void update(int beg, int end, int l, int r,
            int pos, int val)
{
  
    // Push the current node value to
    // left and right subtree
    if (lazy[pos] < INT_MAX)
        pushdown(beg, end, pos);
  
    // If inside the range, then update
    // the value as per the conditions
    if (l <= beg and r >= end
        && tag_condition(pos, val)) {
        lazy[pos] = min(lazy[pos], val);
        pushdown(beg, end, pos);
        return;
    }
  
    // Outside the range
    else if (l > end || r < beg
             || beg > end
             || tree[pos].mx1 <= val) {
        return;
    }
  
    // Check for left and right subtree
    else {
  
        int mid = (beg + end) / 2;
        update(beg, mid, l, r,
               2 * pos + 1, val);
        update(mid + 1, end, l, r,
               2 * pos + 2, val);
        combine(pos);
    }
}
  
// Function that returns the maximum
// value in range [L, R]
int query1(int beg, int end, int l,
           int r, int pos)
{
  
    // Push the current node value in
    // the left and right subtree
    if (lazy[pos] < INT_MAX) {
        pushdown(beg, end, pos);
    }
  
    // If inside the range, then return
    // the maximum value
    if (l <= beg && r >= end) {
        return tree[pos].mx1;
    }
  
    // Outside the range
    else if (l > end || r < beg
             || beg > end) {
        return 0;
    }
  
    // Check for left and right subtree
    else {
        int mid = (beg + end) / 2;
        return max(query1(beg, mid, l, r,
                          2 * pos + 1),
                   query1(mid + 1, end, l,
                          r, 2 * pos + 2));
    }
}
  
// Function to find the sum in the
// range [L, R]
int query2(int beg, int end, int l,
           int r, int pos)
{
    // Push the current node value
    if (lazy[pos] < INT_MAX)
        pushdown(beg, end, pos);
  
    // If in the range, return the
    // sum
    if (l <= beg and r >= end)
        return tree[pos].sum;
    else if (l > end || r < beg
             || beg > end) {
        return 0;
    }
  
    // Check for left and right subtree
    else {
        int mid = (beg + end) / 2;
  
        return query2(beg, mid, l, r,
                      2 * pos + 1)
               + query1(mid + 1, end, l,
                        r, 2 * pos + 2);
    }
}
  
// Construct Segment Tree
void constr(int arr[], int beg,
            int end, int pos)
{
    // If only a single node
    if (beg == end) {
        int x = arr[beg];
        tree[pos].sum = x;
        tree[pos].mx1 = x;
  
        tree[pos].cnt_mx1 = 1;
        tree[pos].mx2 = 0;
        tree[pos].cnt_mx2 = 0;
  
        return;
    }
  
    // Recursively update for
    // left and right subtree
    else {
  
        int mid = (beg + end) / 2;
  
        // For Left subtree
        constr(arr, beg, mid, 2 * pos + 1);
  
        // For right subtree
        constr(arr, mid + 1, end, 2 * pos + 2);
  
        // Combine the two left and
        // right subtree
        combine(pos);
    }
}
  
// A utility function to construct
// the segment tree
void construct(int arr[], int n)
{
    for (int i = 0; i < N; i++) {
        lazy[i] = INT_MAX;
    }
  
    // Function call to Construct
    // segment tree
    constr(arr, 0, n - 1, 0);
}
  
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
  
    // Construct segment tree
    construct(arr, 5);
  
    cout << "Maximum in [2, 4] before update: ";
    // Query for maximum in range [0, 4]
    cout << query1(0, 4, 2, 4, 0) << endl;
  
    cout << "Sum in [2, 4] before update: ";
    // Query for sum in range [0, 4]
    cout << query2(0, 4, 2, 4, 0) << endl;
  
    // Update Query
    update(0, 4, 2, 5, 0, 3);
  
    cout << endl;
    cout << "Updated array elements between "
         << "[2, 4] as min(arr[i], 3)" << endl;
    cout << endl;
  
    cout << "Maximum in [2, 4] after update: ";
    // Query for maximum in range [0, 4]
    cout << query1(0, 4, 2, 4, 0) << endl;
  
    cout << "Sum in [2, 4] after update: ";
    // Query for maximum in range [0, 4]
    cout << query2(0, 4, 2, 4, 0) << endl;
  
    return 0;
}
Producción:

Maximum in [2, 4] before update: 5
Sum in [2, 4] before update: 8

Updated array elements between [2, 4] as min(arr[i], 3)

Maximum in [2, 4] after update: 3
Sum in [2, 4] after update: 6

Complejidad del tiempo: O(N*log N)

Publicación traducida automáticamente

Artículo escrito por soham1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *