Suma de rango modificada en una array dada sin actualizaciones

Dada una array arr[] de tamaño N que contiene números distintos del 1 al N en cualquier orden, la tarea es realizar una suma de rango modificada en esta array de acuerdo con las siguientes reglas. 
Para cada índice ‘ i ‘ en la array arr : 
 

• El índice inicial del rango ‘ L ‘ se selecciona como i + 1
• El índice final del rango ‘ R ‘ se selecciona como: 
  • min(arr[i], N-1) ; si arr[i] > i
  • max(i+1, array[i]) ; si arr[i] < i+1
• Para la actualización, los valores en el rango arr[L] a arr[R] se incrementan en 1.
• El rango se encuentra usando la array de entrada y no la array actualizada

Ejemplos: 
 

Entrada: arr[] = {4, 1, 3, 2} 
Salida: 4 2 5 4 
Explicación: 
Para i = 0 -> Elemento en la array de entrada = 4. Por lo tanto, L = 1 y R = min(4, N- 1) = 3. Por lo tanto, todos los elementos de arr[1] a arr[3] se incrementan en 1. Los elementos después de la operación de actualización son {4, 2, 4, 3}. 
Para i = 1 -> Elemento en la array de entrada = 1. Por lo tanto, L = 2 y R = max(1, i+1) = 2. Por lo tanto, todos los elementos desde arr[2] hasta arr[2] se incrementan en 1. Los elementos después de la operación de actualización son {4, 2, 5, 3}. 
Para i = 2 -> Elemento en la array de entrada = 3. Por lo tanto, L = 3 y R = min(3, N-1) = 3. Por lo tanto, todos los elementos desde arr[3] hasta arr[3] se incrementan en 1. Los elementos después de la operación de actualización son {4, 2, 5, 4}. 
Para i = 3 -> La array no se ve afectada. Por lo tanto, los elementos después de la operación de actualización son {4, 2, 5, 4}. 
La array resultante es {4, 2, 5, 4}.
Entrada: arr[] = {2, 1} 
Salida: {2, 2} 
Explicación: 
El primer elemento es 2. Entonces arr[1] se incrementa en 1. Por lo tanto, la array resultante es {2, 2}. 
 

Enfoque ingenuo: El enfoque ingenuo consiste en ejecutar un bucle para cada elemento y aumentar todos los valores de arr[i+1] a arr[min(i+arr[i], N-1)] en 1. La complejidad temporal de este enfoque es O(N ² ) .
Enfoque eficiente: este problema se puede resolver en O(N) usando un espacio extra de O(N). La idea es utilizar el concepto de array de suma de prefijos . Se siguen los siguientes pasos para calcular la respuesta: 
 

• Se declara un arreglo b[] de tamaño N + 1 y todos los elementos se inicializan con 0.
• Para cada elemento arr[i] en la array dada, se suma 1 a b[i+1] y se resta de b[min(i + arr[i], N – 1)+ 1] .
• Luego, se calcula la suma del prefijo de la array b[] .
• Finalmente, arr se actualiza como arr[i] = arr[i] + b[i] .

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

// C++ program to find elements in an array
// after performing range updates.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform the update on the given
// input array arr[].
void update(vector<int>& arr,
            vector<int>& d, int n)
{
 
    // A new array of size N+1 is defined
    // and 1's are added in that array
    for (int i = 0; i < n - 1; i++) {
        d[i + 1] += 1;
        d[min(i + arr[i], n - 1) + 1] -= 1;
    }
 
    // Loop to perform the prefix sum
    // on the array d[].
    for (int i = 1; i < n; i++) {
        d[i] = d[i] + d[i - 1];
    }
}
 
// Function to print the final
// array after updation
void print(vector<int>& arr,
           vector<int>& d, int n)
{
 
    // Loop to add the values of d[i]
    // to arr[i]
    for (int i = 0; i < n; i++)
        cout << arr[i] + d[i] << " ";
}
 
// Function to perform modified range sum
void modifiedRangeSum(vector<int>& arr, int n)
{
 
    vector<int> d;
 
    // Loop to add N+1 0's in array d[]
    for (int i = 0; i <= n; i++)
        d.push_back(0);
 
    update(arr, d, n);
    print(arr, d, n);
}
 
// Driver code
int main()
{
    vector<int> arr = { 5, 4, 1, 3, 2 };
    int n = 5;
 
    modifiedRangeSum(arr, n);
 
    return 0;
}

// Java program to find elements in an array
// after performing range updates.
import java.util.*;
 
class GFG{
 
static ArrayList<Integer> arr = new
        ArrayList<Integer>(Arrays.asList(5, 4, 1, 3, 2));
static int n = 5;
 
// Function to perform the update on the given
// input array arr[].
static void update(ArrayList<Integer> d)
{
 
    // A new array of size N+1 is defined
    // and 1's are added in that array
    for (int i = 0; i < n - 1; i++) {
        d.set(i + 1,d.get(i+1)+1);
        int x = Math.min(i + arr.get(i), n - 1)+ 1;
        d.set(x,d.get(x)-1);
    }
 
    // Loop to perform the prefix sum
    // on the array d[].
    for (int i = 1; i < n; i++) {
        d.set(i,d.get(i)+d.get(i - 1));
    }
}
 
// Function to print the final
// array after updation
static void print(ArrayList<Integer> d)
{
 
    // Loop to add the values of d[i]
    // to arr[i]
    for (int i = 0; i < n; i++)
        System.out.print(arr.get(i) + d.get(i)+ " ");
}
 
// Function to perform modified range sum
static void modifiedRangeSum()
{
 
    ArrayList<Integer> d = new ArrayList<Integer>();
 
    // Loop to add N+1 0's in array d[]
    for (int i = 0; i <= n; i++)
        d.add(0);
 
    update(d);
    print(d);
}
 
// Driver code
public static void main(String args[])
{
    modifiedRangeSum();
}
}
 
// This code is contributed by Surendra_Gangwar

# Python3 program to find elements in an array
# after performing range updates.
arr = []
d = []
 
# Function to perform the update on the given
# input array arr[].
def update( n):
     
    global d
    global arr
 
    # A new array of size N+1 is defined
    # and 1's are added in that array
    for i in range(n - 1):
        d[i + 1] += 1
        d[min(i + arr[i], n - 1) + 1] -= 1
     
    # Loop to perform the prefix sum
    # on the array d[].
    for i in range(n):
        d[i + 1] = d[i + 1] + d[i ]
     
# Function to print the final
# array after updation
def print_( n):
     
    global d
    global arr
 
    # Loop to add the values of d[i]
    # to arr[i]
    for i in range(n):
        x = (arr[i] + d[i] )
        print(x, end = " ")
 
# Function to perform modified range sum
def modifiedRangeSum( n):
 
    global d
    global arr
 
    d = []
     
    # Loop to add N+1 0's in array d[]
    for i in range(n + 1):
        d.append(0)
 
    update( n)
    print_(n)
 
# Driver code
arr = [5, 4, 1, 3, 2]
n = 5
 
modifiedRangeSum( n)
 
# This code is contributed by Arnab Kundu

// C# program to find elements in an array
// after performing range updates.
 
using System;
       
class GFG {
 
// Function to perform the update on the given
// input array arr[].
static void update(int []arr,int [] d, int n){
  
    // A new array of size N+1 is defined
    // and 1's are added in that array
    for (int i = 0; i < n - 1; i++) {
        d[i + 1] += 1;
        d[Math.Min(i + arr[i], n - 1) + 1] -= 1;
    }
  
    // Loop to perform the prefix sum
    // on the array d[].
    for (int i = 1; i < n; i++) {
        d[i] = d[i] + d[i - 1];
    }
}
  
// Function to print the final
// array after updation
static void print(int []arr,int []d, int n)
{
  
    // Loop to add the values of d[i]
    // to arr[i]
    for (int i = 0; i < n; i++)
        Console.Write((arr[i] + d[i])+" ");
}
  
// Function to perform modified range sum
static void modifiedRangeSum(int []arr, int n)
{
    int []d= new int[n+1];
  
    // Loop to add N+1 0's in array d[]
    for (int i = 0; i <= n; i++)
        d[i]=0;
  
    update(arr, d, n);
    print(arr, d, n);
}
 
// Driver code
public static void Main()
  {
    int [] arr = { 5, 4, 1, 3, 2 };
    int n = 5;
  
    modifiedRangeSum(arr, n);
  }
} 
 
// This code is contributed by mohit kumar 29

<script>
 
// Javascript program to find elements in an array
// after performing range updates.
 
// Function to perform the update on the given
// input array arr[].
function update(arr, d, n)
{
 
    // A new array of size N+1 is defined
    // and 1's are added in that array
    for (var i = 0; i < n - 1; i++) {
        d[i + 1] += 1;
        d[Math.min(i + arr[i], n - 1) + 1] -= 1;
    }
 
    // Loop to perform the prefix sum
    // on the array d[].
    for (var i = 1; i < n; i++) {
        d[i] = d[i] + d[i - 1];
    }
}
 
// Function to print the final
// array after updation
function print(arr, d, n)
{
 
    // Loop to add the values of d[i]
    // to arr[i]
    for (var i = 0; i < n; i++)
        document.write( arr[i] + d[i] + " ");
}
 
// Function to perform modified range sum
function modifiedRangeSum(arr, n)
{
 
    var d = [];
 
    // Loop to add N+1 0's in array d[]
    for (var i = 0; i <= n; i++)
        d.push(0);
 
    update(arr, d, n);
    print(arr, d, n);
}
 
// Driver code
var arr = [5, 4, 1, 3, 2];
var n = 5;
modifiedRangeSum(arr, n);
 
// This code is contributed by importantly.
</script>

5 5 3 6 5