نظرًا لمصفوفة بالحجم N والتي تمت تهيئتها بجميع الأصفار. لقد حصلنا على العديد من النطاقات التي تضيف استعلامات والتي يجب تطبيقها على هذه المصفوفة. نحن بحاجة إلى طباعة المصفوفة المحدثة النهائية كنتيجة لدينا.
أمثلة:
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.
يمكن حل هذه المشكلة باستخدام شجرة المقاطع مع التحديثات البطيئة في وقت O(log N) لكل استعلام ولكن يمكننا أن نفعل ما هو أفضل هنا حيث لم يتم توفير عملية التحديث. يمكننا معالجة كل استعلام في وقت ثابت باستخدام هذا المنطق عندما يتم إعطاء استعلام لإضافة V في النطاق [a b] سنضيف V إلى arr[a] و –V إلى arr[b+1] الآن إذا أردنا الحصول على القيم الفعلية للمصفوفة، فسنقوم بتحويل المصفوفة أعلاه إلى مصفوفة مجموع البادئة.
متى تم اختراع أول جهاز كمبيوتر
انظر المثال أدناه لفهم:
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.
لذا، في الواقع، عندما نضيف قيمة V إلى فهرس محدد للمصفوفة، فهي تمثل إضافة V إلى جميع العناصر الموجودة في هذا الفهرس مباشرةً، ولهذا السبب نضيف –V بعد النطاق لإزالة تأثيره بعد نطاق استعلام الإضافة الخاص به.
يرجى ملاحظة أنه في الكود أدناه إذا امتد النطاق حتى الفهرس الأخير، فسيتم حذف إضافة –V لتكون في حد ذاكرة المصفوفة.
تطبيق:
مجموعات في جافا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>
الإخراج
100 200 300 200 100 100
تعقيد الوقت: O(n)
المساحة المساعدة: O(1)
إنشاء اختبار