一種可以準確進行范圍查詢的方式，

資料結構： Summed Area Table (SAT)
演算法：prefix sum 前綴和

一維

對于一個存放texture的一維陣列，構建一個等大的summed area table，這個table中每個元素的值是texture陣列中該位置元素以及其左側所有元素的總和，
S A T ( i ) = ∑ j ≤ i T e x t u r e ( j ) SAT(i) = \sum_{\mathclap{j\le i}} Texture(j) SAT(i)=j≤i?∑?Texture(j)
示意：

在(a,b]范圍內元素和的計算方式：
R Q ( ( a , b ] ) = S A T ( b ) ? S A T ( a ) RQ((a,b]) = SAT(b) - SAT(a) RQ((a,b])=SAT(b)?SAT(a)

二維

對于一個存放texture的二維陣列，構建一個等大的summed area table，
每個元素的值記錄的是texture陣列中該元素以及其左側和上方的所有元素的總和，
S A T ( x , y ) = ∑ x ′ ≤ x , y ′ ≤ y T e x t u r e ( x ′ , y ′ ) SAT(x,y)=\sum_{x'\le x, y'\le y} Texture(x',y') SAT(x,y)=x′≤x,y′≤y∑?Texture(x′,y′)
示意：

圖中藍色部分元素和的計算方式：
R Q ( D ) = S A T ( D ) ? S A T ( C ) ? S A T ( B ) + S A T ( A ) RQ(D) = SAT(D) - SAT(C) - SAT(B) + SAT(A) RQ(D)=SAT(D)?SAT(C)?SAT(B)+SAT(A)
其中，
S A T ( A ) = S A T ( A x ′ , A y ′ ) SAT(A) = SAT(A_{x'},A_{y'}) SAT(A)=SAT(Ax′?,Ay′?)

分析

時間復雜度O(M*N)
空間復雜度O(M*N)

資料精度會稍有損失，但是影響不大，
二維SAT進行計算時，行與行之間是獨立的，可以并行計算，