Gitt en matrise med størrelse N som er initialisert med alle nuller. Vi får mange områder som legger til spørringer som bør brukes på denne matrisen. Vi må skrive ut den endelige oppdaterte matrisen som resultat.
Eksempler:
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.
Dette problemet kan løses ved hjelp av segmenttre med late oppdateringer i O(log N) tid per spørring, men vi kan gjøre det bedre her siden oppdateringsoperasjon ikke er gitt. Vi kan behandle hver spørring i konstant tid ved å bruke denne logikken når en spørring for å legge til V er gitt i området [a b] vi vil legge til V til arr[a] og –V til arr[b+1] nå hvis vi ønsker å få de faktiske verdiene til matrisen vil vi konvertere ovennevnte matrise til prefikssummatrise.
Se eksemplet nedenfor for å forstå:
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.
Så i realiteten når vi legger til en verdi V til spesifikk indeks for matrisen, representerer det å legge V til alle elementer rett til denne indeksen, det er derfor vi legger til –V etter område for å fjerne effekten etter rekkevidden av add-spørringen.
Vennligst merk i koden nedenfor hvis området strekker seg til siste indeks at tillegget av –V er utelatt for å være i minnegrensen til matrisen.
Implementering:
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>
Produksjon
100 200 300 200 100 100
Tidskompleksitet: O(n)
Hjelpeområde: O(1)
Lag quiz