差異數組|O(1)中的范圍更新查詢 · GeeksForGeeks 中文系列教程

# 差異數組|`O(1)`中的范圍更新查詢 > 原文： [https://www.geeksforgeeks.org/difference-array-range-update-query-o1/](https://www.geeksforgeeks.org/difference-array-range-update-query-o1/) 考慮一個由整數組成的數組`A[]`并遵循以下兩種類型的查詢。 1. `update(l, r, x)`：將`x`加到從`A[l]`到`A[r]`的所有值中（包括兩端）。 2. `printArray()`：打印當前修改后的數組。 **示例**： ``` Input : A [] { 10, 5, 20, 40 } update(0, 1, 10) printArray() update(1, 3, 20) update(2, 2, 30) printArray() Output : 20 15 20 40 20 35 70 60 Explanation : The query update(0, 1, 10) adds 10 to A[0] and A[1]. After update, A[] becomes {20, 15, 20, 40} Query update(1, 3, 20) adds 20 to A[1], A[2] and A[3]. After update, A[] becomes {20, 35, 40, 60}. Query update(2, 2, 30) adds 30 to A[2]. After update, A[] becomes {20, 35, 70, 60}. ``` 一個**簡單解決方案**要執行以下操作： 1. `update(l, r, x)`：從`l`到`r`運行循環，并將`x`添加到從`A[l]`到`A[r]`的所有元素中 2. `printArray()`：僅打印`A[]`。以上兩個操作的時間復雜度為`O(n)` **有效解決方案**是使用差分數組。 **給定數組`A[i]`的差數組**`D[i]`定義為`D[i] = A[i] - A[i-1]`（對于`0 < i < N`）和`D[0] = A[0]`，考慮基于 0 的索引。差值數組可用于執行范圍更新查詢`l r x`，其中`l`是左索引，`r`是右索引，`x`是要添加的值，在所有查詢之后，您都可以從中返回原始數組。可以以`O(1)`復雜度執行更新范圍操作的地方。 1. `update(l, r, x)`：將`x`添加到`D[l]`并將其從`D[r + 1]`中減去，即我們做`D[l] += x`，`D[r + 1] -= x` 2. `printArray()`：執行`A[0] = D[0]`并打印。對于其余元素，執行`A[i] = A[i-1] + D[i]`并打印它們。這里更新的時間復雜度提高到`O(1)`。請注意，`printArray()`仍需要`O(n)`時間。 ## C++ ```cpp // C++ code to demonstrate Difference Array #include <bits/stdc++.h> using namespace std; // Creates a diff array D[] for A[] and returns // it after filling initial values. vector<int> initializeDiffArray(vector<int>& A) { ????int n = A.size(); ????// We use one extra space because ????// update(l, r, x) updates D[r+1] ????vector<int> D(n + 1); ????D[0] = A[0], D[n] = 0; ????for (int i = 1; i < n; i++) ????????D[i] = A[i] - A[i - 1]; ????return D; } // Does range update void update(vector<int>& D, int l, int r, int x) { ????D[l] += x; ????D[r + 1] -= x; } // Prints updated Array int printArray(vector<int>& A, vector<int>& D) { ????for (int i = 0; i < A.size(); i++) { ????????if (i == 0) ????????????A[i] = D[i]; ????????// Note that A[0] or D[0] decides ????????// values of rest of the elements. ????????else ????????????A[i] = D[i] + A[i - 1]; ????????cout << A[i] << " "; ????} ????cout << endl; } // Driver Code int main() { ????// Array to be updated ????vector<int> A{ 10, 5, 20, 40 }; ????// Create and fill difference Array ????vector<int> D = initializeDiffArray(A); ????// After below update(l, r, x), the ????// elements should become 20, 15, 20, 40 ????update(D, 0, 1, 10); ????printArray(A, D); ????// After below updates, the ????// array should become 30, 35, 70, 60 ????update(D, 1, 3, 20); ????update(D, 2, 2, 30); ????printArray(A, D); ????return 0; } ```