Dato un array di dimensione N inizializzato con tutti zeri. Ci vengono forniti molti intervalli per aggiungere query che dovrebbero essere applicate a questo array. Dobbiamo stampare l'array aggiornato finale come risultato.
Esempi:
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.
Questo problema può essere risolto utilizzando albero di segmenti con aggiornamenti lenti in O (log N) tempo per query, ma qui possiamo fare meglio poiché l'operazione di aggiornamento non viene fornita. Possiamo elaborare ogni query in tempo costante utilizzando questa logica quando una query per aggiungere V viene fornita nell'intervallo [a b] aggiungeremo V ad arr[a] e –V ad arr[b+1] ora se vogliamo ottenere i valori effettivi dell'array convertiremo l'array sopra nell'array di somma prefisso.
Vedi l'esempio qui sotto per capire:
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.
Quindi, in effetti, quando aggiungiamo un valore V all'indice specifico dell'array, rappresenta l'aggiunta di V a tutti gli elementi direttamente a questo indice, ecco perché aggiungiamo –V dopo l'intervallo per rimuovere il suo effetto dopo l'intervallo della query di aggiunta.
Si prega di notare nel codice seguente se l'intervallo si estende fino all'ultimo indice, l'aggiunta di –V viene omessa per essere nel limite di memoria dell'array.
Attuazione:
C++// C++ program to get updated array after many array range // add operation #include
// 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 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# 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 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 ?> <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(arrNlohival) { arr[lo] += val; if (hi != N - 1) arr[hi + 1] -= val; } // Utility method to get actual array from // operation array function updateArray(arrN) { // 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(arrN) { updateArray(arr N); for (let i = 0; i < N; i++) document.write('' + arr[i] + ' '); document.write('
'); } // 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>
Produzione
100 200 300 200 100 100
Complessità temporale: O(n)
Spazio ausiliario: O(1)
Crea quiz