M x N boyutunda bir matris verildiğinde, alt matris toplamlarını bulmak için çok sayıda sorgu vardır. Sorguların girdileri, toplamı bulunacak olan alt matrisin sol üst ve sağ alt dizinleridir. 

Alt matris toplam sorgularının O(1) zamanında gerçekleştirilebilmesi için matrisin ön işlenmesi nasıl yapılır. 

Örnek:

  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)

Saf Algoritma:  

Tüm sorguları döngüye alabilir ve her sorguyu, geniş bir sayı aralığı için çok büyük olan O (q*(N*M)) en kötü durumda hesaplayabiliriz.

// 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) 

Optimize Edilmiş Çözüm: 

Toplam Alan Tablosu bu tür bir sorguyu O(M*N) ön işleme süresine indirgeyebilir ve her sorgu O(1) içinde yürütülür. Toplanan Alan Tablosu, bir ızgaranın dikdörtgen bir alt kümesindeki değerlerin toplamını hızlı ve verimli bir şekilde oluşturmaya yönelik bir veri yapısı ve algoritmadır. 

Toplam alan tablosundaki herhangi bir (x y) noktasındaki değer, (x y) dahil olmak üzere yukarıdaki ve solundaki tüm değerlerin toplamıdır:

Optimize edilmiş çözüm aşağıdaki yazıda uygulanmıştır.

  Optimize edilmiş yaklaşımın uygulanması