C++-এ ম্যাট্রিক্সের প্রিফিক্স সম (Prefix Sum of Matrix / 2D Array)

এই সমস্যাতে, একটি ২D ইন্টিজার অ্যারে (ম্যাট্রিক্স) দেওয়া থাকে। এর প্রিফিক্স সম ম্যাট্রিক্স প্রিন্ট করতে হবে।

প্রিফিক্স সম ম্যাট্রিক্স

প্রতিটি উপাদান prefixSum[i][j] = (i,j) উপাদানের উপরের ও বামের সব উপাদানের যোগফল।

prefixSum[i][j] = mat[i][j] + mat[i-1][j] + ... + mat[0][j] 
                + mat[i][j-1] + ... + mat[i][0]

কার্যকর ফর্মুলা

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] 
                - prefixSum[i-1][j-1] + a[i][j]

বিশেষ কেস

i=j=0: prefixSum[0][0] = a[0][0]
i=0, j>0: prefixSum[0][j] = prefixSum[0][j-1] + a[0][j]
i>0, j=0: prefixSum[i][0] = prefixSum[i-1][0] + a[i][0]

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
using namespace std;

#define R 3
#define C 3

void printPrefixSum(int a[][C]) {
    int prefixSum[R][C];
    prefixSum[0][0] = a[0][0];
    
    for (int i = 1; i < C; i++)
        prefixSum[0][i] = prefixSum[0][i-1] + a[0][i];
    for (int i = 1; i < R; i++)
        prefixSum[i][0] = prefixSum[i-1][0] + a[i][0];
    
    for (int i = 1; i < R; i++) {
        for (int j = 1; j < C; j++)
            prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] 
                            - prefixSum[i-1][j-1] + a[i][j];
    }
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++)
            cout << prefixSum[i][j] << "\t";
        cout << endl;
    }
}

int main() {
    int mat[R][C] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    cout << "The prefix Sum Matrix is:\n";
    printPrefixSum(mat);
    return 0;
}

আউটপুট

1   3   6
5   12  21
12  27  45