Tiền tố tổng của ma trận (hoặc mảng 2D) trong C++

Trong bài toán này, chúng ta được cho một mảng 2D các giá trị nguyên mat[][]. Nhiệm vụ của chúng ta là in ma trận tiền tố tổng của mat.

Ma trận tiền tố tổng: mọi phần tử của ma trận là tổng các phần tử phía trên và bên trái của nó. Tức là

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

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: arr =[
    [4  6  1]
    [5  7  2]
    [3  8  9] ]
Đầu ra:[
    [4  10  11]
    [9  22  25]
    [12  33  45] ]

Để giải quyết bài toán này, một giải pháp đơn giản là tìm prefixSum bằng cách duyệt tất cả các phần tử đến vị trí i,j và cộng chúng. Nhưng nó hơi phức tạp cho hệ thống.

Một giải pháp hiệu quả hơn sẽ là sử dụng công thức để tìm giá trị các phần tử của ma trận prefixSum.

Công thức chung cho phần tử ở vị trí ij là

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

Một số trường hợp đặc biệt:

Với i = j = 0, prefixSum[i][j] = a[i][j]
Với i = 0 và j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j]
Với i > 0 và j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]

Mã minh họa triển khai giải pháp của chúng ta:

Ví dụ

#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 = 0; 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<<"Ma trận tiền tố tổng là :\n";
    printPrefixSum(mat);
    return 0;
}

Kết quả

Ma trận tiền tố tổng là :
1   3   6
5   12  21
12  27  45