Dané pole o velikosti N, které je inicializováno všemi nulami. Dostali jsme mnoho rozsahů přidaných dotazů, které by měly být aplikovány na toto pole. Potřebujeme vytisknout konečné aktualizované pole jako náš výsledek.
Příklady:
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.
Tento problém lze vyřešit pomocí segmentový strom s línými aktualizacemi v O(log N) čas na dotaz, ale můžeme to udělat lépe, protože operace aktualizace není dána. Pomocí této logiky můžeme zpracovávat každý dotaz v konstantním čase, když je dotaz na přidání V dán v rozsahu [a b] přidáme V k arr[a] a –V k arr[b+1] nyní, pokud chceme získat skutečné hodnoty pole, převedeme výše uvedené pole na pole součtů prefixů.
Pro pochopení viz níže uvedený příklad:
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.
Takže ve skutečnosti, když přidáme hodnotu V ke specifickému indexu pole, představuje to přidání V ke všem prvkům přímo k tomuto indexu, proto přidáváme –V za rozsah, abychom odstranili jeho účinek po jeho rozsahu dotazu na přidání.
Všimněte si prosím v níže uvedeném kódu, pokud rozsah zasahuje do posledního indexu, přidání –V je vynecháno, aby bylo v limitu paměti pole.
Implementace:
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>
Výstup
100 200 300 200 100 100
Časová složitost: O(n)
Pomocný prostor: O(1)
Vytvořit kvíz