Dada una array de tamaño N que se inicializa con todos ceros. Se nos dan muchos rangos para agregar consultas, que deben aplicarse a esta array. Necesitamos imprimir la array actualizada final como nuestro resultado.
Ejemplos:
N = 6 Arr = [0, 0, 0, 0, 0, 0] rangeUpdate1 [0, 2], add 100 Arr = [100, 100, 100, 0, 0, 0] rangeUpdate1 [1, 5], add 100 Arr = [100, 200, 200, 100, 100, 100] rangeUpdate1 [2, 3], add 100 Arr = [100, 200, 300, 200, 100, 100] Which is the final updated array.
Este problema se puede resolver utilizando un árbol de segmentos con actualizaciones perezosas en tiempo O (log N) por consulta, pero podemos hacerlo mejor aquí, ya que no se proporciona la operación de actualización. Podemos procesar cada consulta en tiempo constante usando esta lógica cuando se da una consulta para agregar V en el rango [a, b]. Agregaremos V a arr[a] y –V a arr[b+1] ahora si queremos obtener los valores reales de la array, convertiremos la array anterior en una array de suma de prefijos.
Vea el siguiente ejemplo para entender:
Arr = [0, 0, 0, 0, 0, 0] rangeUpdate1 [0, 2], add 100 Arr = [100, 0, 0, -100, 0, 0] rangeUpdate1 [1, 5], add 100. Arr = [100, 100, 0, -100, 0, 0] Note: You can not add -100 at 6th index because array length is 6. rangeUpdate1 [2, 3], add 100 Arr = [100, 100, 100, -100, -100, 0] Now we will convert above operation array to prefix sum array as shown below, Arr = [100, 200, 300, 200, 100, 100] Which is the final updated array.
Entonces, en efecto, cuando agregamos un valor V a un índice específico de la array, representa agregar V a todos los elementos directamente a este índice, es por eso que agregamos -V después del rango para eliminar su efecto después de su rango de agregar consulta.
Tenga en cuenta que en el código a continuación, si el rango se extiende hasta el último índice, se omite la adición de -V para estar en el límite de memoria de la array.
Implementación:
C++
// C++ program to get updated array after many array range
// add operation
#include <bits/stdc++.h>
using namespace std;
// Utility method to add value val, to range [lo, hi]
void add(int arr[], int N, int lo, int hi, int val)
{
arr[lo] += val;
if (hi != N - 1)
arr[hi + 1] -= val;
}
// Utility method to get actual array from operation array
void updateArray(int arr[], int N)
{
// convert array into prefix sum array
for (int i = 1; i < N; i++)
arr[i] += arr[i - 1];
}
// method to print final updated array
void printArr(int arr[], int N)
{
updateArray(arr, N);
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int N = 6;
int arr[N] = {0};
// Range add Queries
add(arr, N, 0, 2, 100);
add(arr, N, 1, 5, 100);
add(arr, N, 2, 3, 100);
printArr(arr, N);
return 0;
}
Java
// Java program to get updated array after
// many array range add operation
import java.io.*;
class GFG {
// Utility method to add value val,
// to range [lo, hi]
static void add(int arr[], int N, int lo, int hi,
int val)
{
arr[lo] += val;
if (hi != N - 1)
arr[hi + 1] -= val;
}
// Utility method to get actual array from
// operation array
static void updateArray(int arr[], int N)
{
// convert array into prefix sum array
for (int i = 1; i < N; i++)
arr[i] += arr[i - 1];
}
// method to print final updated array
static void printArr(int arr[], int N)
{
updateArray(arr, N);
for (int i = 0; i < N; i++)
System.out.print("" + arr[i] + " ");
System.out.print("\n");
}
// Driver code
public static void main(String[] args)
{
int N = 6;
int arr[] = new int[N];
// Range add Queries
add(arr, N, 0, 2, 100);
add(arr, N, 1, 5, 100);
add(arr, N, 2, 3, 100);
printArr(arr, N);
}
}
// This code is contributed by Prakriti Gupta
Python3
# Python3 program to get updated array # after many array range add operation # Utility method to add value # val, to range [lo, hi] def add(arr, N, lo, hi, val): arr[lo] += val if (hi != N - 1): arr[hi + 1] -= val # Utility method to get actual # array from operation array def updateArray(arr, N): # convert array into prefix sum array for i in range(1, N): arr[i] += arr[i - 1] # method to print final updated array def printArr(arr, N): updateArray(arr, N) for i in range(N): print(arr[i], end=" ") print() # Driver code N = 6 arr = [0 for i in range(N)] # Range add Queries add(arr, N, 0, 2, 100) add(arr, N, 1, 5, 100) add(arr, N, 2, 3, 100) printArr(arr, N) # This code is contributed by Anant Agarwal.
C#
// C# program to get updated array after
// many array range add operation
using System;
class GFG {
// Utility method to add value val,
// to range [lo, hi]
static void add(int[] arr, int N, int lo, int hi,
int val)
{
arr[lo] += val;
if (hi != N - 1)
arr[hi + 1] -= val;
}
// Utility method to get actual
// array from operation array
static void updateArray(int[] arr, int N)
{
// convert array into
// prefix sum array
for (int i = 1; i < N; i++)
arr[i] += arr[i - 1];
}
// method to print final updated array
static void printArr(int[] arr, int N)
{
updateArray(arr, N);
for (int i = 0; i < N; i++)
Console.Write("" + arr[i] + " ");
Console.Write("\n");
}
// Driver code
public static void Main()
{
int N = 6;
int[] arr = new int[N];
// Range add Queries
add(arr, N, 0, 2, 100);
add(arr, N, 1, 5, 100);
add(arr, N, 2, 3, 100);
printArr(arr, N);
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to get updated array after
// many array range add operation
// Utility method to add value val,
// to range [lo, hi]
function add(&$arr, $N, $lo, $hi, $val)
{
$arr[$lo] += $val;
if ($hi != $N - 1)
$arr[$hi + 1] -= $val;
}
// Utility method to get actual array
// from operation array
function updateArray(&$arr, $N)
{
// convert array into prefix sum array
for ($i = 1; $i < $N; $i++)
$arr[$i] += $arr[$i - 1];
}
// method to print final updated array
function printArr(&$arr, $N)
{
updateArray($arr, $N);
for ($i = 0; $i < $N; $i++)
echo $arr[$i] . " ";
echo "\n";
}
// Driver Code
$N = 6;
$arr = array_fill(0, $N, NULL);
// Range add Queries
add($arr, $N, 0, 2, 100);
add($arr, $N, 1, 5, 100);
add($arr, $N, 2, 3, 100);
printArr($arr, $N);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to get updated array after
// many array range add operation
// Utility method to add value val,
// to range [lo, hi]
function add(arr,N,lo,hi,val)
{
arr[lo] += val;
if (hi != N - 1)
arr[hi + 1] -= val;
}
// Utility method to get actual array from
// operation array
function updateArray(arr,N)
{
// convert array into prefix sum array
for (let i = 1; i < N; i++)
arr[i] += arr[i - 1];
}
// method to print final updated array
function printArr(arr,N)
{
updateArray(arr, N);
for (let i = 0; i < N; i++)
document.write("" + arr[i] + " ");
document.write("<br>");
}
// Driver code
let N = 6;
let arr=new Array(N);
for(let i=0;i<N;i++)
{
arr[i]=0;
}
// Range add Queries
add(arr, N, 0, 2, 100);
add(arr, N, 1, 5, 100);
add(arr, N, 2, 3, 100);
printArr(arr, N);
// This code is contributed by rag2127
</script>
100 200 300 200 100 100
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA