Prefix sums and differences are fundamental techniques in algorithm design, particularly for efficient range operations on arrays.
Prefix Sums
Purpose: Prefix sums enable quick calculation of range sums in an array by precomputing cumulative sums. This allows O(1) range sum queries.
Implementation: For an array A of length n, the prefix sum array S is computed as:
S = [0] * (n + 1)
for i in range(n):
S[i + 1] = S[i] + A[i]
Range Query: The sum from index l to r is computed as S[r + 1] - S[l].
Difference Technique
Purpose: The difference technique efficient handles range updates by maintaining a difference array that tracks changes between adjacent elements.
Implementation: For an array A, the difference array D is:
D = [0] * (n + 2)
D[1] = A[0]
for i in range(1, n):
D[i + 1] = A[i] - A[i - 1]
Range Udpate: To add x to elements from l to r:
D[l] += x
D[r + 1] -= x
Recovering Array: The original array can be reconstructed by computing the prefix sum of D.
Comlpexity Analysis
| Technique | Query Time | Update Time | Preprocessing | Space |
|---|---|---|---|---|
| Naive | O(n) | O(n) | O(1) | O(1) |
| Prefix Sum | O(1) | O(n) | O(n) | O(n) |
| Difference | O(n) | O(1) | O(n) | O(n) |
Applications
- Prefix Sums: Ideal for problems requiring frequent range sum queries.
- Difference: Best for problems involving frequent range updates.
2D Extensions
Both techniques can be extended to two-dimensional arrays for matrix operations:
# 2D Prefix Sum
prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j]
# 2D Difference
diff = [[0] * (n + 2) for _ in range(m + 2)]
# Update operation
diff[x1][y1] += val
diff[x1][y2 + 1] -= val
diff[x2 + 1][y1] -= val
diff[x2 + 1][y2 + 1] += val