如何在O(1)复杂度下计算越界二维数组子集的平均值？

Great question! The summed area table (SAT) approach you're already using can absolutely be adapted to handle out-of-bounds cases while retaining that O(1) query efficiency—no fancy new filtering techniques required, just a few simple bounds checks and adjustments.

Here's the step-by-step solution: #

First, make sure you're using the standard (n+1)×(m+1) SAT structure for your original array (where n and m are the array's height and width). This structure has a row and column of zeros along the top and left edges, which simplifies boundary calculations.

For any query defining a subset from (x1, y1) to (x2, y2) (closed interval, assuming 0-based indexing):

1. Clamp the query coordinates to the original array's valid bounds:

   • For your 4×4 example, the valid row indices are 0–3, valid column indices are 0–3.
   • Calculate:

     clamped_x1 = max(x1, 0)
     clamped_x2 = min(x2, 3)
     clamped_y1 = max(y1, 0)
     clamped_y2 = min(y2, 3)
     

   This gives you the portion of the query that actually overlaps with the original array (the rest is treated as zeros).

2. Calculate the sum of the valid overlapping region:

   • If clamped_x1 > clamped_x2 or clamped_y1 > clamped_y2, the entire query is out of bounds—sum is 0.
   • Otherwise, use the standard SAT sum formula:

     sum = SAT[clamped_x2 + 1][clamped_y2 + 1] - SAT[clamped_x1][clamped_y2 + 1] - SAT[clamped_x2 + 1][clamped_y1] + SAT[clamped_x1][clamped_y1]
     

   This gives you the sum of all non-zero elements in the query subset.

3. Compute the total area of the query subset:

   • Even though out-of-bounds elements are zero, they still count towards the denominator for the average. Calculate the full area:

     area = (x2 - x1 + 1) * (y2 - y1 + 1)
     

4. Calculate the average:

   • Divide the valid sum by the full area: average = sum / area

Let's test this with your example: #

Your query is from (2,2) to (4,4) on a 4×4 array:

• Clamped coordinates: clamped_x1=2, clamped_x2=3, clamped_y1=2, clamped_y2=3
• SAT sum calculation:
  • SAT[4][4] (sum of entire array) = 120
  • SAT[2][4] (sum of first 2 rows) = 28
  • SAT[4][2] (sum of first 2 columns) = 52
  • SAT[2][2] (sum of top-left 2×2 subset) = 10
  • Sum = 120 - 28 - 52 + 10 = 50
• Area = (4-2+1)*(4-2+1) = 9
• Average = 50/9 (matches your expected result)

Key Notes: #

• This approach maintains O(1) query time—all operations (clamping, SAT lookup, area calculation) are constant-time.
• For a 2000×2000 array, building the SAT takes O(nm) time (one pass through the array), which is efficient and only done once.
• No extra memory is needed (unlike padding the array with zeros beforehand), making it optimal for large arrays.

内容的提问来源于stack exchange，提问作者JiPecki