Difference Array


By magicalsoup
Written 26 days ago

Introduction

We have learned prefix sum arrays before (if not, go read that lesson!), they are built in \(O(N)\) time and can answer summation queries in \(O(1)\) time. However, we learned that it cannot update in \(O(1)\) time, and is a static data structure. Difference arrays are here to make a difference. They can update a range in \(O(1)\) time, and take \(O(N)\) time to build, however they cannot do summation queries in \(O(1)\) time.

How to build difference arrays.

As the name suggests, the difference array stores the difference between every adjacent element, a standard implementation of building the array is shown below:

Dif[0] = A[0]; // there is no element before this element
Dif[n] = 0;  // we allocate one more space at the end of the difference array for updates, and we set it to 0 
for(int i = 1; i < n; i++) {
    Dif[i] = A[i] - A[i - 1]; // get the adjacent differences and store them in the difference array
}

As the for loop suggests, this build takes \(O(N)\) time to build.

Time Complexity: \(O(N)\)

Executing updates

The difference array can update a range, using a property of summation. Here, prefix sum arrays comes in as well. If we need to update a range, we can simply use prefix sum array and carry the sum over a range, by only marking the starting index of the update, and marking the ending index of the update with the negative value of the update value, this way the summation cancels out after updating that range.

Thus, we can update an range by just marking \(2\) indexes with a value, and do prefix sum array on the difference array to get back the original array after updating. The below code demonstrates an update.

int l, r, x; 
cin>>l>>r>>x;
dif[l] += x;
dif[r+1] -= x;

To get back the original array, we will do prefix sum on the difference array.

for(int i=1; i<n; i++) {
   dif[i] += dif[i-1];
}

Conclusion

We have introduced a nice property of summation and also a nice conversion between prefix sum array and difference arrays. Here is the whole list.

Lets say the prefix sum array is \(psa\), difference array is \(dif\), and the original array is \(A\).

  • We can do prefix sum from \(A\) to get \(psa\). We can do difference from \(psa\) to get \(A\).
  • We can do difference from \(A\) to get \(dif\). We can do prefix sum from \(dif\) to get \(A\).
  • We can do two times prefix sum to get from \(dif\) to \(psa\). We can do two times difference to get from \(psa\) to \(dif\).

Difference array can update over a range in \(O(1)\) time, and takes \(O(N)\) time to build, however, it cannot to summation over a range in \(O(1)\) time, since we need to do 2 times prefix sum to get the prefix sum array, which takes \(O(N)\) time.

Time Complexity: \(O(N)\) build and \(O(1)\) queries and total time complexity of \(O(N + Q)\), where \(N\) is the size of the list and \(Q\) is the number of queries.