すべて 0 で初期化されたサイズ 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] で指定された場合、このロジックを使用して各クエリを定数時間で処理できます。配列の実際の値を取得したい場合は、上記の配列をプレフィックス合計配列に変換します。
理解するには、以下の例を参照してください。
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)
クイズの作成