數組上的恒定時間范圍添加操作 · GeeksForGeeks 中文系列教程

# 數組上的恒定時間范圍添加操作 > 原文： [https://www.geeksforgeeks.org/constant-time-range-add-operation-array/](https://www.geeksforgeeks.org/constant-time-range-add-operation-array/) 給定大小為`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)`時間中使用](https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/)延遲更新來解決此問題，但是由于沒有給出更新操作，因此我們可以在這里做得更好。我們可以使用此邏輯在恒定時間內處理每個查詢，當在范圍`[a, b]`中給出添加`V`的查詢時，如果需要，我們現在將`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, -100] rangeUpdate1 [2, 3], add 100 Arr = [100, 100, 100, -100, -100, 0, -100] 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`添加至該索引的所有元素，這就是為什么我們在`range`之后添加`–V`以在其`add`查詢范圍之后刪除其影響。請在下面的代碼中注意，如果范圍跨度到最后一個索引，則`-V`的加法被省略，因為它在數組的內存限制內。 ## C++ ```cpp //? C++ program to get updated array after many array range // add operation #include <bits/stdc++.h> using namespace std; //? Utility method to add value val, to range [lo, hi] 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 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 void printArr(int arr[], int N) { ????updateArray(arr, N); ????for (int i = 0; i < N; i++) ????????cout << arr[i] << " "; ????cout << endl; } //? Driver code to test above methods int main() { ????int N = 6; ????int arr[N] = {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); ????return 0; } ```