בהינתן מטריצה ​​בגודל M x N יש מספר רב של שאילתות למציאת סכומי תת-מטריקס. כניסות לשאילתות הן אינדקסים משמאל למעלה וימין למטה של ​​תת-מטריקס שסכומם הוא לברר. 

כיצד לעבד מראש את המטריצה ​​כך שניתן לבצע שאילתות סכום תת-מטריקס בזמן O(1). 

דוּגמָה:

  tli :   Row number of top left of query submatrix   tlj :   Column number of top left of query submatrix   rbi :   Row number of bottom right of query submatrix   rbj :   Column number of bottom right of query submatrix Input: mat[M][N] = {{1 2 3 4 6} {5 3 8 1 2} {4 6 7 5 5} {2 4 8 9 4} }; Query1: tli = 0 tlj = 0 rbi = 1 rbj = 1 Query2: tli = 2 tlj = 2 rbi = 3 rbj = 4 Query3: tli = 1 tlj = 2 rbi = 3 rbj = 3; Output: Query1: 11 // Sum between (0 0) and (1 1) Query2: 38 // Sum between (2 2) and (3 4) Query3: 38 // Sum between (1 2) and (3 3)

אלגוריתם נאיבי:  

אנחנו יכולים בלולאה את כל השאילתות ולחשב כל שאילתה ב-O (q*(N*M)) המקרה הגרוע ביותר שהוא גדול מדי עבור טווח גדול של מספרים.

// Pseudo code of Naive algorithm. Arr[][] = input_matrix For each query: Input tli tlj rbi rbj sum = 0 for i from tli to tbi (inclusive): for j from tlj to rbj(inclusive): sum += Arr[i][j] print(sum) 

פתרון אופטימלי: 

טבלת שטח מסוכם יכול לצמצם סוג זה של שאילתה לזמן עיבוד מקדים של O(M*N) וכל שאילתה תבוצע ב-O(1). Summed Area Table הוא מבנה נתונים ואלגוריתם להפקה מהירה ויעילה של סכום הערכים בתת-קבוצה מלבנית של רשת. 

הערך בכל נקודה (x y) בטבלת השטח המסוכמת הוא רק הסכום של כל הערכים מעל ומשמאל ל-(x y) כולל:

הפתרון האופטימלי מיושם בפוסט למטה.

  יישום גישה אופטימלית