➕ Prefix Sum & Difference Arrays

[tpemeja]

Summary

• Patterns

  • Prefix Sum (1D): cumulative sums; O(1) range queries; count subarrays by value/constraint; balances via remapping; supports negatives with hash maps.
  • Prefix Sum (2D): extra row/col; O(1) submatrix sums; row-pair compression for counting/constraints.
  • Difference Arrays: O(1) range updates; reconstruct via prefix; works in 1D/2D; great for many updates then one read.

• Choose

  • Many static range-sum queries → Prefix Sum (1D/2D)
  • Count subarrays/submatrices by exact sum or divisibility → Prefix Sum + hash map
  • Many range increments, single final array → Difference Array (1D/2D)

Details

✅ Prefix Sum (1D)

Summary (Key points):

• Precompute cumulative sums once to answer any subarray sum in O(1).
• Exclusive prefix: P[0]=0; P[i+1]=P[i]+A[i]; sum A[l..r]=P[r+1]−P[l].
• Count subarrays by mapping needed prior prefixes: freq[cur−k] (sum==k) or freq[cur%k] (divisible by k).
• Handles negatives naturally via hash maps; great for balance/remapping tricks.
• Time O(n) to build/scan; space O(n) in counting variants.

Details

• Concept recap:

  • Build P of length n+1 with P[0]=0; P[i+1]=P[i]+A[i].
  • Range query: sum(l..r)=P[r+1]−P[l].
  • Counting: maintain running cur; answer += freq[cur−k]; then freq[cur]++.
  • Divisibility: track remainders cur%k; equal remainders form divisible subarrays.

• Generic template:

  # Build prefix and query (exclusive prefix)
  def prefix_sums(a):
      n = len(a)
      P = [0] * (n + 1)
      for i in range(n):
          P[i+1] = P[i] + a[i]
      return P
  
  def range_sum(P, l, r):  # inclusive l..r
      return P[r+1] - P[l]

  # Count subarrays with sum == k (works with negatives)
  from collections import defaultdict
  def count_subarrays_sum_k(a, k):
      freq = defaultdict(int)
      freq[0] = 1
      cur = 0
      ans = 0
      for x in a:
          cur += x
          ans += freq[cur - k]
          freq[cur] += 1
      return ans

  # Count subarrays with sum divisible by k
  from collections import defaultdict
  def count_divisible_by_k(a, k):
      freq = defaultdict(int)
      freq[0] = 1
      cur = 0
      ans = 0
      for x in a:
          cur = (cur + x) % k
          ans += freq[cur]
          freq[cur] += 1
      return ans

• Case 1: Subarray Sum Equals K

  • Maintain running sum; for each cur, add freq[cur−k], then freq[cur]++.
  • Time: O(n), Space: O(n).

  from collections import defaultdict
  def subarraySum(nums, k):
      freq = defaultdict(int); freq[0] = 1
      cur = ans = 0
      for x in nums:
          cur += x
          ans += freq[cur - k]
          freq[cur] += 1
      return ans

• Case 2: Subarray Sums Divisible by K

  • Equal prefix remainders imply divisible subarray; count pairs by remainder freq.
  • Time: O(n), Space: O(k) up to O(n).

  from collections import defaultdict
  def subarraysDivByK(nums, k):
      freq = defaultdict(int); freq[0] = 1
      cur = ans = 0
      for x in nums:
          cur = (cur + x) % k
          ans += freq[cur]
          freq[cur] += 1
      return ans

• Case 3: Continuous Subarray Sum

  • Exists subarray len ≥ 2 with sum % k == 0: store earliest index per remainder.
  • Time: O(n), Space: O(k) up to O(n).

  def checkSubarraySum(nums, k):
      seen = {0: -1}
      cur = 0
      for i, x in enumerate(nums):
          cur = (cur + x) % k
          if cur in seen:
              if i - seen[cur] >= 2:
                  return True
          else:
              seen[cur] = i
      return False

• Case 4: Find Pivot Index

  • total = sum(nums); scan with left; check left == total - left - nums[i].
  • Time: O(n), Space: O(1).

  def pivotIndex(nums):
      total = sum(nums)
      left = 0
      for i, x in enumerate(nums):
          if left == total - left - x:
              return i
          left += x
      return -1

• Case 5: Range Sum Query – Immutable

  • Precompute P once; each query O(1).
  • Time: O(n + q), Space: O(n).

  class NumArray:
      def __init__(self, nums):
          n = len(nums)
          self.P = [0] * (n + 1)
          for i in range(n):
              self.P[i+1] = self.P[i] + nums[i]
      def sumRange(self, left, right):
          return self.P[right+1] - self.P[left]

• Case 6: Sum of Absolute Differences in a Sorted Array

  • Split contribution: left uses xi - P[i]; right uses (P[n]-P[i+1]) - x(n-i-1).
  • Time: O(n), Space: O(n).

  def getSumAbsoluteDifferences(nums):
      n = len(nums)
      P = [0] * (n + 1)
      for i in range(n):
          P[i+1] = P[i] + nums[i]
      res = [0] * n
      for i, x in enumerate(nums):
          left = x * i - P[i]
          right = (P[n] - P[i+1]) - x * (n - i - 1)
          res[i] = left + right
      return res

• Case 7: Minimum Average Difference

  • Track left_sum and derive right_sum from total; compare integer averages.
  • Time: O(n), Space: O(1).

  def minimumAverageDifference(nums):
      n = len(nums)
      total = sum(nums)
      left = 0
      best_diff, best_i = 10**18, 0
      for i, x in enumerate(nums):
          left += x
          left_avg = left // (i + 1)
          if i == n - 1:
              right_avg = 0
          else:
              right_avg = (total - left) // (n - i - 1)
          diff = abs(left_avg - right_avg)
          if diff < best_diff:
              best_diff, best_i = diff, i
      return best_i

• Pitfalls and tips:

  • Prefer exclusive prefix (length n+1) to avoid l−1 checks.
  • Any array mutation invalidates P; rebuild or use Fenwick/Segment Tree for frequent updates.
  • Mod with negatives (language-dependent): normalize to [0, k) via (x % k + k) % k.
  • For longest subarray variants, store earliest index of a prefix value/remainder.

• Complexity summary:

  • Build prefix once (O(n)); each range query O(1).
  • Counting scans are O(n) time with up to O(n) extra map space.

✅ Prefix Sum (2D)

Summary (Key points):

• Build 2D prefix with extra top row and left column of zeros.
• Query any submatrix sum in O(1): sum[r1..r2][c1..c2] = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1].
• For counting/constraints: compress between row pairs into 1D and apply 1D techniques with hash maps or BST.
• Time O(mn) to build; O(1) per sum query; counting/constraint patterns often O(min(m,n)^2 · max(m,n)).

Details

• Concept recap:

  • P has shape (m+1)×(n+1), P[0][]=P[][0]=0.
  • Build: P[i+1][j+1] = P[i+1][j] + P[i][j+1] − P[i][j] + A[i][j].
  • Query: sum(r1..r2, c1..c2) via 4-lookups inclusion–exclusion.

• Generic template:

  def prefix2d(mat):
      m = len(mat)
      n = len(mat[0]) if m else 0
      P = [[0] * (n + 1) for _ in range(m + 1)]
      for i in range(m):
          for j in range(n):
              P[i+1][j+1] = P[i+1][j] + P[i][j+1] - P[i][j] + mat[i][j]
      return P
  
  def sum_region(P, r1, c1, r2, c2):
      # inclusive r1..r2, c1..c2
      return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

• Case 1: Range Sum Query 2D – Immutable

  • Precompute 2D prefix; each query O(1).
  • Time: O(mn), Space: O(mn).

  class NumMatrix:
      def __init__(self, matrix):
          m = len(matrix)
          n = len(matrix[0]) if m else 0
          self.P = [[0] * (n + 1) for _ in range(m + 1)]
          for i in range(m):
              for j in range(n):
                  self.P[i+1][j+1] = (
                      self.P[i+1][j] + self.P[i][j+1] - self.P[i][j] + matrix[i][j]
                  )
  
      def sumRegion(self, r1, c1, r2, c2):
          P = self.P
          return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

• Case 2: Number of Submatrices That Sum to Target

  • Fix top row; expand bottom; compress columns to 1D sums; count subarrays equal to target with hash map.
  • Time: O(m^2·n) if m ≤ n (or O(n^2·m) otherwise), Space: O(n).

  from collections import defaultdict
  
  def numSubmatrixSumTarget(matrix, target):
      m, n = len(matrix), len(matrix[0])
      # Prefix per row to speed segment sums on columns
      rowP = [[0] * (n + 1) for _ in range(m)]
      for i in range(m):
          for j in range(n):
              rowP[i][j+1] = rowP[i][j] + matrix[i][j]
  
      ans = 0
      for c1 in range(n):
          for c2 in range(c1, n):
              freq = defaultdict(int)
              freq[0] = 1
              cur = 0
              for r in range(m):
                  cur += rowP[r][c2+1] - rowP[r][c1]
                  ans += freq[cur - target]
                  freq[cur] += 1
      return ans

• Case 3: Max Sum of Rectangle No Larger Than K

  • Row-pair compression to 1D; then “max subarray sum ≤ k” via sorted prefix sums + binary search.
  • Time: O(min(m,n)^2 · max(m,n) · log max(m,n)), Space: O(max(m,n)).

  import bisect
  
  def maxSumSubmatrix(matrix, k):
      m, n = len(matrix), len(matrix[0])
      # Ensure fewer rows than cols for speed (optional)
      if m > n:
          matrix = list(map(list, zip(*matrix)))
          m, n = n, m
  
      ans = -10**18
      for top in range(m):
          arr = [0] * n
          for bottom in range(top, m):
              for c in range(n):
                  arr[c] += matrix[bottom][c]
              # Now find max subarray sum <= k in arr
              prefix = [0]
              cur = 0
              best = -10**18
              for x in arr:
                  cur += x
                  # Find smallest prefix >= cur - k
                  i = bisect.bisect_left(prefix, cur - k)
                  if i < len(prefix):
                      best = max(best, cur - prefix[i])
                  bisect.insort(prefix, cur)
              ans = max(ans, best)
              if ans == k:
                  return k
      return ans

• Case 4: Matrix Block Sum

  • Use 2D prefix; each cell’s block sum is a clamped submatrix query.
  • Time: O(mn), Space: O(mn).

  def matrixBlockSum(mat, k):
      m, n = len(mat), len(mat[0])
      P = [[0] * (n + 1) for _ in range(m + 1)]
      for i in range(m):
          for j in range(n):
              P[i+1][j+1] = P[i+1][j] + P[i][j+1] - P[i][j] + mat[i][j]
  
      def q(r1, c1, r2, c2):
          r1 = max(r1, 0); c1 = max(c1, 0)
          r2 = min(r2, m - 1); c2 = min(c2, n - 1)
          if r1 > r2 or c1 > c2:
              return 0
          return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
  
      ans = [[0] * n for _ in range(m)]
      for i in range(m):
          for j in range(n):
              ans[i][j] = q(i - k, j - k, i + k, j + k)
      return ans

• Pitfalls and tips:

  • Off-by-one: always allocate +1 in both dimensions and use r+1/c+1 in queries.
  • When counting rectangles, iterate over the smaller dimension for row/col pairing.
  • Large values: use 64-bit integers (Python auto-handles big ints).
  • Prefix XOR (variant): similar build, but with XOR and inclusion–exclusion for XOR queries.

• Complexity summary:

  • Build: O(mn); Query: O(1).
  • Counting/constraint problems: typically O(min(m,n)^2 · max(m,n)) with extra data structures.

✅ Difference Arrays

Summary (Key points):

• Convert range updates to O(1) boundary ops; reconstruct final array by prefix summing once.
• 1D: D[l]+=x; D[r+1]−=x; final[i] = prefix(D) + base[i].
• 2D: mark rectangle corners with inclusion–exclusion; reconstruct via 2D prefix.
• Ideal for many updates then one read; supports strings (shifts) and timelines (capacity checks).
• Time O(q + n) for 1D (or O(q + mn) for 2D); extra space proportional to base size.

Details

• Concept recap (1D):

  • Start with D of length n+1 zeros.
  • For each range add [l, r] by x: D[l]+=x; D[r+1]−=x.
  • Reconstruct: sweep prefix of D and add to base to get final.

• Generic template (1D):

  def apply_range_additions(n, updates):
      """
      n: array length
      updates: list of (l, r, x), inclusive
      returns the resulting array after applying all increments to zeros
      """
      D = [0] * (n + 1)
      for l, r, x in updates:
          D[l] += x
          D[r + 1] -= x
      res = [0] * n
      cur = 0
      for i in range(n):
          cur += D[i]
          res[i] = cur
      return res

• 2D difference (rectangle updates):

  # To add x to rectangle [r1..r2][c1..c2] inclusive:
  # D[r1][c1] += x
  # D[r1][c2+1] -= x
  # D[r2+1][c1] -= x
  # D[r2+1][c2+1] += x
  # Then reconstruct final by 2D prefix on D.

• Case 1: Range Addition

  • Apply updates with difference array; reconstruct to get final array.
  • Time: O(k + n), Space: O(n).

  def getModifiedArray(n, updates):
      D = [0] * (n + 1)
      for l, r, inc in updates:
          D[l] += inc
          if r + 1 <= n - 1:
              D[r + 1] -= inc
      res = [0] * n
      cur = 0
      for i in range(n):
          cur += D[i]
          res[i] = cur
      return res

• Case 2: Corporate Flight Bookings

  • Bookings [l, r, seats] (1-indexed). Use difference array and prefix.
  • Time: O(m + n), Space: O(n).

  def corpFlightBookings(bookings, n):
      D = [0] * (n + 1)
      for l, r, seats in bookings:
          D[l - 1] += seats     # shift to 0-index
          if r < n:
              D[r] -= seats
      res = [0] * n
      cur = 0
      for i in range(n):
          cur += D[i]
          res[i] = cur
      return res

• Case 3: Car Pooling

  • Trips [passengers, start, end): difference on timeline; check capacity never exceeded.
  • Time: O(T + U), Space: O(T) where T is coordinate range (or compress).

  def carPooling(trips, capacity):
      max_pos = 0
      for p, s, e in trips:
          max_pos = max(max_pos, e)
      D = [0] * (max_pos + 1)
      for p, s, e in trips:
          D[s] += p
          D[e] -= p
      cur = 0
      for x in range(max_pos + 1):
          cur += D[x]
          if cur > capacity:
              return False
      return True

• Case 4: Shifting Letters II

  • Range character shifts using difference; apply final shifts modulo 26.
  • Time: O(n + q), Space: O(n).

  def shiftingLetters(s, shifts):
      n = len(s)
      D = [0] * (n + 1)
      for l, r, d in shifts:
          delta = 1 if d == 1 else -1
          D[l] += delta
          if r + 1 < len(D):
              D[r + 1] -= delta
      add = 0
      res = []
      for i, ch in enumerate(s):
          add += D[i]
          k = (ord(ch) - 97 + add) % 26
          res.append(chr(97 + k))
      return "".join(res)

• Pitfalls and tips:

  • Boundaries: always guard r+1 index; difference array typically length n+1.
  • Multiple bases: if starting array A is non-zero, reconstruct as A[i] + prefix(D)[i].
  • 2D: allocate (m+1)×(n+1) for D; reconstruct via 2D prefix (same inclusion–exclusion as 2D sums).
  • Coordinate compression: for large sparse coordinates (e.g., car pooling with large positions), compress keys first.

• Complexity summary:

  • 1D: O(q + n) time to apply q updates and build; O(n) space.
  • 2D: O(q + mn) time to apply and reconstruct; O(mn) space.

[tpemeja]

1D :

https://newsletter.francofernando.com/p/range-queries

2D:

Create bigger matrix (n+1, m+1)
Top only zero, right only zero
And after
B[i+1, j+1] = sum du carre de A[0,0] à A[i,j]

Donc pour calculer B[i+1, j+1] il faut prendre tout ce qui est en haut, tout ce qui est a gauche et enlever B[i, j] puis que compter en double et ajouter la value de A[i,j] qui n'est dans aucune des deux.

En ensuite quand on veut la somme de r1, c1 à r2, c2, il faut prendre B[r2+1, c2+1] - B[r2+1, c1] - B[r1, c2+1] + B[r1 c1]

https://newsletter.francofernando.com/p/range-queries https://archive.mcpt.ca/cpt-lessons/advanced/2d-prefix-sum-array/