# 多次數組范圍遞增操作后打印修改后的數組 > 原文： [https://www.geeksforgeeks.org/print-modified-array-multiple-array-range-increment-operations/](https://www.geeksforgeeks.org/print-modified-array-multiple-array-range-increment-operations/) 給定一個包含 **n** 整數和值 **d** 的數組。 給出 **m 個**查詢。 每個查詢具有兩個值**開始**和**結束**。 對于每個查詢，問題是將給定數組中從**開始**到**結束**索引的值增加給定值 **d** 。 需要線性省時的解決方案來處理此類多個查詢。 **示例**： ``` Input : arr[] = {3, 5, 4, 8, 6, 1} Query list: {0, 3}, {4, 5}, {1, 4}, {0, 1}, {2, 5} d = 2 Output : 7 11 10 14 12 5 Executing 1st query {0, 3} arr = {5, 7, 6, 10, 6, 1} Executing 2nd query {4, 5} arr = {5, 7, 6, 10, 8, 3} Executing 3rd query {1, 4} arr = {5, 9, 8, 12, 10, 3} Executing 4th query {0, 1} arr = {7, 11, 8, 12, 10, 3} Executing 5th query {2, 5} arr = {7, 11, 10, 14, 12, 5} Note: Each query is executed on the previously modified array. ``` **樸素的方法**：對于每個查詢，遍歷**開始**到**結束**范圍內的數組，并將該范圍內的值增加給定值 **d** 。 **有效方法**：創建大小為 **n** 的數組 **sum []** 并將其所有索引初始化為 0。現在，對于每個**（開始， end）**索引對在 **sum []** 數組上應用給定的運算。 僅當存在索引**（end + 1）**時，操作才是 **sum [start] + = d** 和 **sum [end + 1]-= d** 。 現在，從索引 **i** = 1 到 n-1，將 **sum []** 數組中的值累加為： **sum [i] + = sum [i-1 ]** 。 最后，對于索引 **i** = 0 到 n-1，執行以下操作： **arr [i] + = sum [i]** 。 ## C++ ```cpp // C++ implementation to increment values in the // given range by a value d for multiple queries #include <bits/stdc++.h> using namespace std; // structure to store the (start, end) index pair for // each query struct query { ????int start, end; }; // function to increment values in the given range // by a value d for multiple queries void incrementByD(int arr[], struct query q_arr[], ??????????????????int n, int m, int d) { ????int sum[n]; ????memset(sum, 0, sizeof(sum)); ????// for each (start, end) index pair perform the ????// following operations on 'sum[]' ????for (int i = 0; i < m; i++) { ????????// increment the value at index 'start' by ????????// the given value 'd' in 'sum[]' ????????sum[q_arr[i].start] += d; ????????// if the index '(end+1)' exists then decrement? ????????// the value at index '(end+1)' by the given? ????????// value 'd' in 'sum[]' ????????if ((q_arr[i].end + 1) < n) ????????????sum[q_arr[i].end + 1] -= d; ????} ????// Now, perform the following operations: ????// accumulate values in the 'sum[]' array and? ????// then add them to the corresponding indexes ????// in 'arr[]' ????arr[0] += sum[0]; ????for (int i = 1; i < n; i++) { ????????sum[i] += sum[i - 1]; ????????arr[i] += sum[i]; ????} } // function to print the elements of the given array void printArray(int arr[], int n) { ????for (int i = 0; i < n; i++) ????????cout << arr[i] << " "; } // Driver program to test above int main() { ????int arr[] = { 3, 5, 4, 8, 6, 1 }; ????struct query q_arr[] = { { 0, 3 }, { 4, 5 }, { 1, 4 },? ???????????????????????????????????????{ 0, 1 }, { 2, 5 } }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int m = sizeof(q_arr) / sizeof(q_arr[0]); ????int d = 2; ????cout << "Original Array:\n"; ????printArray(arr, n); ????// modifying the array for multiple queries ????incrementByD(arr, q_arr, n, m, d); ????cout << "\nModified Array:\n"; ????printArray(arr, n); ????return 0; } ``` ## Java ```java // Java implementation to increment values in the? // given range by a value d for multiple queries class GFG? { ????// structure to store the (start, end)? ????// index pair for each query ????static class query ????{ ????????int start, end; ????????query(int start, int end)? ????????{ ????????????this.start = start; ????????????this.end = end; ????????} ????} ????// function to increment values in the given range ????// by a value d for multiple queries ????public static void incrementByD(int[] arr, query[] q_arr, ????????????????????????????????????int n, int m, int d)? ????{ ????????int[] sum = new int[n]; ????????// for each (start, end) index pair, perform? ????????// the following operations on 'sum[]' ????????for (int i = 0; i < m; i++) ????????{ ????????????// increment the value at index 'start'? ????????????// by the given value 'd' in 'sum[]' ????????????sum[q_arr[i].start] += d; ????????????// if the index '(end+1)' exists then? ????????????// decrement the value at index '(end+1)'? ????????????// by the given value 'd' in 'sum[]' ????????????if ((q_arr[i].end + 1) < n) ????????????????sum[q_arr[i].end + 1] -= d; ????????} ????????// Now, perform the following operations: ????????// accumulate values in the 'sum[]' array and ????????// then add them to the corresponding indexes ????????// in 'arr[]' ????????arr[0] += sum[0]; ????????for (int i = 1; i < n; i++) ????????{ ????????????sum[i] += sum[i - 1]; ????????????arr[i] += sum[i]; ????????} ????} ????// function to print the elements of the given array ????public static void printArray(int[] arr, int n) ????{ ????????for (int i = 0; i < n; i++) ????????????System.out.print(arr[i] + " "); ????} ????// Driver code ????public static void main(String[] args) ????{ ????????int[] arr = { 3, 5, 4, 8, 6, 1 }; ????????query[] q_arr = new query[5]; ????????q_arr[0] = new query(0, 3); ????????q_arr[1] = new query(4, 5); ????????q_arr[2] = new query(1, 4); ????????q_arr[3] = new query(0, 1); ????????q_arr[4] = new query(2, 5); ????????int n = arr.length; ????????int m = q_arr.length; ????????int d = 2; ????????System.out.println("Original Array:"); ????????printArray(arr, n); ????????// modifying the array for multiple queries ????????incrementByD(arr, q_arr, n, m, d); ????????System.out.println("\nModified Array:"); ????????printArray(arr, n); ????} } // This code is contributed by // sanjeev2552 ``` ## Python3 ```py # Python3 implementation to increment? # values in the given range by a value d? # for multiple queries # structure to store the (start, end)? # index pair for each query # function to increment values in the given range # by a value d for multiple queries def incrementByD(arr, q_arr, n, m, d): ????sum = [0 for i in range(n)] ????# for each (start, end) index pair perform? ????# the following operations on 'sum[]' ????for i in range(m): ????????# increment the value at index 'start'? ????????# by the given value 'd' in 'sum[]' ????????sum[q_arr[i][0]] += d ????????# if the index '(end+1)' exists then decrement ????????# the value at index '(end+1)' by the given ????????# value 'd' in 'sum[]' ????????if ((q_arr[i][1] + 1) < n): ????????????sum[q_arr[i][1] + 1] -= d ????# Now, perform the following operations: ????# accumulate values in the 'sum[]' array and ????# then add them to the corresponding indexes ????# in 'arr[]' ????arr[0] += sum[0] ????for i in range(1, n): ????????sum[i] += sum[i - 1] ????????arr[i] += sum[i] # function to print the elements? # of the given array def printArray(arr, n): ????for i in arr: ????????print(i, end = " ") # Driver Code arr = [ 3, 5, 4, 8, 6, 1] q_arr = [[0, 3], [4, 5], [1, 4], ?????????[0, 1], [2, 5]] n = len(arr) m = len(q_arr) d = 2 print("Original Array:") printArray(arr, n) # modifying the array for multiple queries incrementByD(arr, q_arr, n, m, d) print("\nModified Array:") printArray(arr, n) # This code is contributed # by Mohit Kumar ``` ## C# ```cs // C# implementation to increment values in the? // given range by a value d for multiple queries using System; class GFG? { ????// structure to store the (start, end)? ????// index pair for each query ????public class query ????{ ????????public int start, end; ????????public query(int start, int end)? ????????{ ????????????this.start = start; ????????????this.end = end; ????????} ????} ????// function to increment values in the given range ????// by a value d for multiple queries ????public static void incrementByD(int[] arr, query[] q_arr, ????????????????????????????????????int n, int m, int d)? ????{ ????????int[] sum = new int[n]; ????????// for each (start, end) index pair, perform? ????????// the following operations on 'sum[]' ????????for (int i = 0; i < m; i++) ????????{ ????????????// increment the value at index 'start'? ????????????// by the given value 'd' in 'sum[]' ????????????sum[q_arr[i].start] += d; ????????????// if the index '(end+1)' exists then? ????????????// decrement the value at index '(end+1)'? ????????????// by the given value 'd' in 'sum[]' ????????????if ((q_arr[i].end + 1) < n) ????????????????sum[q_arr[i].end + 1] -= d; ????????} ????????// Now, perform the following operations: ????????// accumulate values in the 'sum[]' array and ????????// then add them to the corresponding indexes ????????// in 'arr[]' ????????arr[0] += sum[0]; ????????for (int i = 1; i < n; i++) ????????{ ????????????sum[i] += sum[i - 1]; ????????????arr[i] += sum[i]; ????????} ????} ????// function to print the elements of the given array ????public static void printArray(int[] arr, int n) ????{ ????????for (int i = 0; i < n; i++) ????????????Console.Write(arr[i] + " "); ????} ????// Driver code ????public static void Main(String[] args) ????{ ????????int[] arr = { 3, 5, 4, 8, 6, 1 }; ????????query[] q_arr = new query[5]; ????????q_arr[0] = new query(0, 3); ????????q_arr[1] = new query(4, 5); ????????q_arr[2] = new query(1, 4); ????????q_arr[3] = new query(0, 1); ????????q_arr[4] = new query(2, 5); ????????int n = arr.Length; ????????int m = q_arr.Length; ????????int d = 2; ????????Console.WriteLine("Original Array:"); ????????printArray(arr, n); ????????// modifying the array for multiple queries ????????incrementByD(arr, q_arr, n, m, d); ????????Console.WriteLine("\nModified Array:"); ????????printArray(arr, n); ????} } // This code is contributed by Princi Singh ``` **輸出**： ``` Original Array: 3 5 4 8 6 1 Modified Array: 7 11 10 14 12 5 ``` **時間復雜度**： O（m + n） **輔助空間**：`O(n)`