Consultas para incrementar los elementos de la array en un rango dado por un valor dado por un número dado de veces

Dada una array , arr[] de N enteros positivos y M consultas de la forma {a, b, val, f} . La tarea es imprimir la array después de realizar cada consulta para incrementar los elementos de la array en el rango [a, b] por un valor val f varias veces.

Ejemplos:

Entrada: arr[] = {1, 2, 3}, M=3, Q[][] = {{1, 2, 1, 4}, {1, 3, 2, 3}, {2, 3, 4, 5}}
Salida: 11 32 29
Explicación: 
Después de aplicar la primera consulta 4 veces, 
la array será: 5 6 3
Después de aplicar la segunda consulta 3 veces, 
la array será: 11 12 9
Después de aplicar la tercera consulta 5 veces, 
la array será : 11 32 29
Por lo tanto, la array final será {11, 32, 29}.

Entrada: arr[] = {1}, M = 1, Q[][] = {{1, 1, 1, 1}}
Salida: 2
Explicación: 
Después de aplicar la primera y única consulta solo 1 vez.
La array será: 2

Enfoque ingenuo : el enfoque más simple es realizar cada consulta en la array dada, es decir, para cada consulta {a, b, val, f} recorrer la array en el rango [a, b] y aumentar cada elemento por valor val anúmero f de tiempos Imprima la array después de realizar cada consulta.

Complejidad de tiempo: O(N * M * max(Freq))
Espacio auxiliar: O(1)

Mejor enfoque : la idea se basa en la array de diferencias que se puede usar en las operaciones de actualización de rango. A continuación se muestran los pasos:

1. Encuentre la array de diferencias D[] de una array dada A[] se define como D[i] = (A[i] – A[i – 1]) (0 < i < N) y D[0] = A[ 0] considerando la indexación basada en 0 .
2. Agregue val a D[a – 1] y réstelo de D[(b – 1) + 1] , es decir, D[a – 1] += val, D[(b – 1) + 1] -= val. Realice esta operación Freq número de veces.
3. Ahora actualice la array dada usando la array de diferencias. Actualice A[0] a D[0] e imprímalo. Para el resto de los elementos, haz A[i] = A[i-1] + D[i] .
4. Imprima la array resultante después de los pasos anteriores.

Complejidad de tiempo: O(N + M * max(Freq))
Espacio auxiliar: O(N) Espacio adicional para array de diferencias

Enfoque eficiente :  este enfoque es similar al enfoque anterior, pero es una versión extendida de la aplicación de una array de diferencias. Anteriormente, la tarea era actualizar los valores de los índices a a b por val , f número de veces. Aquí, en lugar de llamar a la función de actualización de rango f varias veces, llámela solo una vez para cada consulta:

1. Actualice los valores de los índices a a b por val*f , solo 1 vez para cada consulta.
2. Agregue val*f a D[a – 1] y réstelo de D[(b – 1) + 1] , es decir, aumente D[a – 1] en val*f y disminuya D[b] en val*f .
3. Ahora actualice la array principal usando la array de diferencias. Actualice A[0] a D[0] e imprímalo.
4. Para el resto de los elementos, actualice A[i] por (A[i-1] + D[i]) .
5. Imprima la array resultante después de los pasos anteriores.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that creates a difference
// array D[] for A[]
vector<int> initializeDiffArray(
    vector<int>& A)
{
    int N = A.size();
 
    // Stores the difference array
    vector<int> D(N + 1);
 
    D[0] = A[0], D[N] = 0;
 
    // Update difference array D[]
    for (int i = 1; i < N; i++)
        D[i] = A[i] - A[i - 1];
 
    // Return difference array
    return D;
}
 
// Function that performs the range
// update queries
void update(vector<int>& D, int l,
            int r, int x)
{
    // Update the ends of the range
    D[l] += x;
    D[r + 1] -= x;
}
 
// Function that perform all query
// once with modified update Call
void UpdateDiffArray(vector<int>& DiffArray,
                     int Start, int End,
                     int Val, int Freq)
{
    // For range update, difference
    // array is modified
    update(DiffArray, Start - 1,
           End - 1, Val * Freq);
}
 
// Function to take queries
void queriesInput(vector<int>& DiffArray,
                  int Q[][4], int M)
{
    // Traverse the query
    for (int i = 0; i < M; i++) {
 
        // Function Call for updates
        UpdateDiffArray(DiffArray, Q[i][0],
                        Q[i][1], Q[i][2],
                        Q[i][3]);
    }
}
 
// Function to updates the array
// using the difference array
void UpdateArray(vector<int>& A,
                 vector<int>& D)
{
    // Traverse the array A[]
    for (int i = 0; i < A.size(); i++) {
 
        // 1st Element
        if (i == 0) {
            A[i] = D[i];
        }
 
        // A[0] or D[0] decides values
        // of rest of the elements
        else {
            A[i] = D[i] + A[i - 1];
        }
    }
}
 
// Function that prints the array
void PrintArray(vector<int>& A)
{
    // Print the element
    for (int i = 0; i < A.size(); i++) {
        cout << A[i] << " ";
    }
 
    return;
}
 
// Function that print the array
// after performing all queries
void printAfterUpdate(vector<int>& A,
                      int Q[][4], int M)
{
    // Create and fill difference
    // array for range updates
    vector<int> DiffArray
        = initializeDiffArray(A);
 
    queriesInput(DiffArray, Q, M);
 
    // Now update Array A using
    // Difference Array
    UpdateArray(A, DiffArray);
 
    // Print updated Array A
    // after M queries
    PrintArray(A);
}
 
// Driver Code
int main()
{
    // N = Array size, M = Queries
    int N = 3, M = 3;
 
    // Given array A[]
    vector<int> A{ 1, 2, 3 };
 
    // Queries
    int Q[][4] = { { 1, 2, 1, 4 },
                   { 1, 3, 2, 3 },
                   { 2, 3, 4, 5 } };
 
    // Function Call
    printAfterUpdate(A, Q, M);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
   
// N = Array size,
// M = Queries
static int N = 3, M = 3;
   
static int []A = new int[N];
 
//Stores the difference array
static int []D = new int[N + 1];
   
// Function that creates
// a difference array D[]
// for A[]
static void initializeDiffArray()
{
  D[0] = A[0];
  D[N] = 0;
 
  // Update difference array D[]
  for (int i = 1; i < N; i++)
    D[i] = A[i] - A[i - 1];
}
 
// Function that performs
// the range update queries
static void update(int l,
                   int r, int x)
{
  // Update the ends
  // of the range
  D[l] += x;
  D[r + 1] -= x;
}
 
// Function that perform all query
// once with modified update Call
static void UpdateDiffArray(int Start, int End,
                            int Val, int Freq)
{
  // For range update, difference
  // array is modified
  update(Start - 1,
         End - 1, Val * Freq);
}
 
// Function to take queries
static void queriesInput(  int Q[][])
{
  // Traverse the query
  for (int i = 0; i < M; i++)
  {
    // Function Call for updates
    UpdateDiffArray(Q[i][0], Q[i][1],
                    Q[i][2], Q[i][3]);
  }
}
 
// Function to updates the array
// using the difference array
static void UpdateArray()
{
  // Traverse the array A[]
  for (int i = 0; i < N; i++)
  {
    // 1st Element
    if (i == 0)
    {
      A[i] = D[i];
    }
 
    // A[0] or D[0] decides
    // values of rest of
    // the elements
    else
    {
      A[i] = D[i] + A[i - 1];
    }
  }
}
 
// Function that prints
// the array
static void PrintArray()
{
  // Print the element
  for (int i = 0; i < N; i++)
  {
    System.out.print(A[i] + i +
                     1 + " ");
  }
  return;
}
 
// Function that print the array
// after performing all queries
static void printAfterUpdate(int []A,
                             int Q[][], int M)
{
  // Create and fill difference
  // array for range updates
  initializeDiffArray();
 
  queriesInput( Q);
 
  // Now update Array
  // A using Difference
  // Array
  UpdateArray();
 
  // Print updated Array A
  // after M queries
  PrintArray();
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array A[]
  int []A = {1, 2, 3};
 
  // Queries
  int [][]Q = {{1, 2, 1, 4},
               {1, 3, 2, 3},
               {2, 3, 4, 5}};
 
  // Function Call
  printAfterUpdate(A, Q, M);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
 
# Function that creates a difference
# array D[] for A[]
def initializeDiffArray(A):
     
    N = len(A)
 
    # Stores the difference array
    D = [0] * (N + 1)
 
    D[0] = A[0]
    D[N] = 0
 
    # Update difference array D[]
    for i in range(1, N):
        D[i] = A[i] - A[i - 1]
 
    # Return difference array
    return D
 
# Function that performs the range
# update queries
def update(D, l, r, x):
     
    # Update the ends of the range
    D[l] += x
    D[r + 1] -= x
 
# Function that perform all query
# once with modified update Call
def UpdateDiffArray(DiffArray, Start,
                    End, Val, Freq):
                         
    # For range update, difference
    # array is modified
    update(DiffArray, Start - 1,
           End - 1, Val * Freq)
 
# Function to take queries
def queriesInput(DiffArray, Q, M):
     
    # Traverse the query
    for i in range(M):
 
        # Function Call for updates
        UpdateDiffArray(DiffArray, Q[i][0],
                          Q[i][1], Q[i][2],
                          Q[i][3])
 
# Function to updates the array
# using the difference array
def UpdateArray(A, D):
     
    # Traverse the array A[]
    for i in range(len(A)):
 
        # 1st Element
        if (i == 0):
            A[i] = D[i]
 
        # A[0] or D[0] decides values
        # of rest of the elements
        else:
            A[i] = D[i] + A[i - 1]
 
# Function that prints the array
def PrintArray(A):
     
    # Print the element
    for i in range(len(A)):
        print(A[i], end = " ")
         
    return
 
# Function that print the array
# after performing all queries
def printAfterUpdate(A, Q, M):
     
    # Create and fill difference
    # array for range updates
    DiffArray = initializeDiffArray(A)
 
    queriesInput(DiffArray, Q, M)
 
    # Now update Array A using
    # Difference Array
    UpdateArray(A, DiffArray)
 
    # Print updated Array A
    # after M queries
    PrintArray(A)
 
# Driver Code
if __name__ == '__main__':
     
    # N = Array size, M = Queries
    N = 3
    M = 3
 
    # Given array A[]
    A = [ 1, 2, 3 ]
 
    # Queries
    Q = [ [ 1, 2, 1, 4 ],
          [ 1, 3, 2, 3 ],
          [ 2, 3, 4, 5 ] ]
 
    # Function call
    printAfterUpdate(A, Q, M)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
class GFG{
 
// N = Array size,
// M = Queries
static int N = 3, M = 3;
 
static int[] A = new int[N];
 
// Stores the difference array
static int[] D = new int[N + 1];
 
// Function that creates
// a difference array D[]
// for A[]
static void initializeDiffArray()
{
  D[0] = A[0];
  D[N] = 0;
 
  // Update difference array D[]
  for (int i = 1; i < N; i++)
    D[i] = A[i] - A[i - 1];
}
 
// Function that performs
// the range update queries
static void update(int l,
                   int r, int x)
{
  // Update the ends
  // of the range
  D[l] += x;
  D[r + 1] -= x;
}
 
// Function that perform all query
// once with modified update Call
static void UpdateDiffArray(int Start, int End,
                            int Val, int Freq)
{
  // For range update, difference
  // array is modified
  update(Start - 1,
         End - 1, Val * Freq);
}
 
// Function to take queries
static void queriesInput(int[, ] Q)
{
  // Traverse the query
  for (int i = 0; i < M; i++)
  {
    // Function Call for updates
    UpdateDiffArray(Q[i, 0], Q[i, 1],
                    Q[i, 2], Q[i, 3]);
  }
}
 
// Function to updates the array
// using the difference array
static void UpdateArray()
{
  // Traverse the array A[]
  for (int i = 0; i < N; i++)
  {
    // 1st Element
    if (i == 0)
    {
      A[i] = D[i];
    }
 
    // A[0] or D[0] decides
    // values of rest of
    // the elements
    else
    {
      A[i] = D[i] + A[i - 1];
    }
  }
}
 
// Function that prints
// the array
static void PrintArray()
{
  // Print the element
  for (int i = 0; i < N; i++)
  {
    Console.Write(A[i] + i +
                  1 + " ");
  }
  return;
}
 
// Function that print the array
// after performing all queries
static void printAfterUpdate(int[] A,
                             int[, ] Q, int M)
{
  // Create and fill difference
  // array for range updates
  initializeDiffArray();
 
  queriesInput(Q);
 
  // Now update Array
  // A using Difference
  // Array
  UpdateArray();
 
  // Print updated Array A
  // after M queries
  PrintArray();
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array A[]
  int[] A = {1, 2, 3};
 
  // Queries
  int[, ] Q = {{1, 2, 1, 4},
               {1, 3, 2, 3},
               {2, 3, 4, 5}};
 
  // Function Call
  printAfterUpdate(A, Q, M);
}
 
// This code is contributed by Chitranayal

<script>
 
// Javascript program to implement
// the above approach
 
// N = Array size,
// M = Queries
let N = 3, M = 3;
   
let A = new Array(N).fill(0);
 
//Stores the difference array
let D = new Array(N+1).fill(0);
   
// Function that creates
// a difference array D[]
// for A[]
function initializeDiffArray()
{
  D[0] = A[0];
  D[N] = 0;
 
  // Update difference array D[]
  for (let i = 1; i < N; i++)
    D[i] = A[i] - A[i - 1];
}
 
// Function that performs
// the range update queries
function update(l, r, x)
{
  // Update the ends
  // of the range
  D[l] += x;
  D[r + 1] -= x;
}
 
// Function that perform all query
// once with modified update Call
function UpdateDiffArray(Start, End, Val, Freq)
{
  // For range update, difference
  // array is modified
  update(Start - 1,
         End - 1, Val * Freq);
}
 
// Function to take queries
function queriesInput(Q)
{
  // Traverse the query
  for (let i = 0; i < M; i++)
  {
    // Function Call for updates
    UpdateDiffArray(Q[i][0], Q[i][1],
                    Q[i][2], Q[i][3]);
  }
}
 
// Function to updates the array
// using the difference array
function UpdateArray()
{
  // Traverse the array A[]
  for (let i = 0; i < N; i++)
  {
    // 1st Element
    if (i == 0)
    {
      A[i] = D[i];
    }
 
    // A[0] or D[0] decides
    // values of rest of
    // the elements
    else
    {
      A[i] = D[i] + A[i - 1];
    }
  }
}
 
// Function that print
// the array
function PrintArray()
{
  // Print the element
  for (let i = 0; i < N; i++)
  {
    document.write(A[i] + i +
                     1 + " ");
  }
  return;
}
 
// Function that print the array
// after performing all queries
function printAfterUpdate(A, Q, M)
{
  // Create and fill difference
  // array for range updates
  initializeDiffArray();
 
  queriesInput( Q);
 
  // Now update Array
  // A using Difference
  // Array
  UpdateArray();
 
  // Print updated Array A
  // after M queries
  PrintArray();
}
 
// Driver Code
 
  
     // Given array A[]
  let a = [1, 2, 3];
 
  // Queries
  let Q = [[1, 2, 1, 4],
               [1, 3, 2, 3],
               [2, 3, 4, 5]];
 
  // Function Call
  printAfterUpdate(a, Q, M);
          
</script>

11 32 29 

Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)