Understanding Difference Arrays

Given an array arr, its difference array diff is defined as:

diff[0] = arr[0]
diff[i] = arr[i] - arr[i-1] for i > 0

To reconstruct the original array from the difference array:

arr[i] = diff[0] + diff[1] + ... + diff[i]

For range updates [l, r] with value x:

diff[l] += x
diff[r+1] -= x

Key properties:

1. Enables efficient range additions
2. Requires batch updates before queries
3. diff[l] += x affects all element from l onward
4. diff[r+1] -= x cencels the effect after r

Practical Example

def range_updates():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    n = int(data[idx])
    m = int(data[idx+1])
    idx += 2
    
    arr = list(map(int, data[idx:idx+n]))
    idx += n
    
    diff = [0] * (n + 2)
    diff[0] = arr[0]
    for i in range(1, n):
        diff[i] = arr[i] - arr[i-1]
    
    for _ in range(m):
        l = int(data[idx]) - 1
        r = int(data[idx+1]) - 1
        val = int(data[idx+2])
        idx += 3
        
        diff[l] += val
        diff[r+1] -= val
    
    arr[0] = diff[0]
    for i in range(1, n):
        arr[i] = arr[i-1] + diff[i]
    
    print(' '.join(map(str, arr)))

range_updates()

2D Difference Arrays

The 2D diffreence array formula:

diff[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1]

To update a rectangular region (x1,y1) to (x2,y2) with value x:

diff[x1][y1] += x
diff[x1][y2+1] -= x
diff[x2+1][y1] -= x
diff[x2+1][y2+1] += x

Implementation example:

def process_2d_array():
    n, m = map(int, input().split())
    matrix = [[0]*(m+2) for _ in range(n+2)]
    diff = [[0]*(m+2) for _ in range(n+2)]
    
    for i in range(1, n+1):
        row = list(map(int, input().split()))
        for j in range(1, m+1):
            matrix[i][j] = row[j-1]
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            diff[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]
    
    # Example update
    x1, y1, x2, y2, val = 1, 1, 2, 2, 5
    diff[x1][y1] += val
    diff[x1][y2+1] -= val
    diff[x2+1][y1] -= val
    diff[x2+1][y2+1] += val
    
    # Reconstruct matrix
    for i in range(1, n+1):
        for j in range(1, m+1):
            matrix[i][j] = matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1] + diff[i][j]
    
    for row in matrix[1:n+1]:
        print(' '.join(map(str, row[1:m+1])))