একটি ২D ম্যাট্রিক্স দেওয়া থাকলে, (row1, col1) থেকে (row2, col2) সাবম্যাট্রিক্সের যোগফল দ্রুত বের করতে হবে।
সমাধানের ধাপসমূহ
- প্রিফিক্স সম ম্যাট্রিক্স
dpতৈরি করুন যেখানেdp[i][j]= (0,0) থেকে (i,j) পর্যন্ত যোগফল। - রো-ওয়াইজ এবং কলাম-ওয়াইজ প্রিফিক্স সম নিয়ে
dpবানান। - কোয়েরি:
sum = dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1]।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
if (!n) return;
int m = matrix[0].size();
dp.assign(n, vector<int>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
dp[i][j] = matrix[i][j] + (j ? dp[i][j-1] : 0);
for (int i = 1; i < n; i++)
for (int j = 0; j < m; j++)
dp[i][j] += dp[i-1][j];
}
int sumRegion(int r1, int c1, int r2, int c2) {
int ret = dp[r2][c2];
int sub1 = r1 ? dp[r1-1][c2] : 0;
int sub2 = c1 ? dp[r2][c1-1] : 0;
int add = (r1 && c1) ? dp[r1-1][c1-1] : 0;
return ret - sub1 - sub2 + add;
}
};
int main() {
vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
NumMatrix ob(mat);
cout << ob.sumRegion(2,1,4,3) << endl; // 8
cout << ob.sumRegion(1,1,2,2) << endl; // 11
cout << ob.sumRegion(1,2,2,4) << endl; // 12
}
ইনপুট
[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)
আউটপুট
8 11 12
