بالنظر إلى مصفوفة بحجم 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) شاملة:

يتم تنفيذ الحل الأمثل في المنشور أدناه.

  تنفيذ النهج الأمثل