Delta Array

[box-lin]

The prefix sum of a delta array is the array itself.

Suppose nums = [1,3,5,2],
It is delta_array = [1, 2, 2, -3],
and the prefix sum of delta_array = [1, 3, 5, 2]

The concept of the prefix sum is somewhat analogous to the integral in calculus. In calculus, we integrate with respect to dx, where dx is an infinitesimally small change in x.

Prefix Sums: A prefix sum array can be used to quickly answer queries about the sum of elements in a range of an array. Once the prefix sum array is computed, the sum of elements in a range between indices i and j can be computed as prefixSum[j] - prefixSum[i-1] (assuming 0-based indexing). This operation is done in constant time O(1), which is extremely efficient.

Delta Arrays: A delta array can be used to perform range updates in an array. That is, if you want to add a value v to all elements in a range between indices i and j in an array, you can do so by adding v to delta[i] and subtracting v from delta[j+1]. Then, the updated array can be obtained by computing the prefix sum of the delta array. This range update operation is done in constant time O(1), which, again, is highly efficient.

Thus, problems that require frequent range updates or range sum queries can benefit significantly from using these techniques.

class Solution:
        """
        suppose we start with [0,0,0...] 
        and we want to eventually match nums.
        
        delta_array[i] and delta_array[j] indicates where a range of addition start and end
        """
    def checkArray(self, nums: List[int], k: int) -> bool:
        acc = 0
        n = len(nums)
        delta_array = [0] * (n+1)
        for i in range(n):
            # the prefix sum of delta_array at each i, should be equal to nums[i]
            acc += delta_array[i]
            if acc == nums[i]: continue 
            if acc > nums[i]: return False # over reach to nums[i]
            # now acc < nums[i], we may need [i,i+k) addition
            # but if i+k is out of index, meaning we can't perform this range operation
            if i+k > n: return False
            # otherwise, updating our delta_array
            delta = nums[i] - acc
            delta_array[i] += delta
            delta_array[i+k] -= delta
            acc += delta
        # note that this only happens when prefix sum of delta_array is equal to nums itself!
        return True