# 差异数组|`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; } ```