Prefix Sum ของเมทริกซ์ (หรือ 2D Array) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ 2D ของค่าจำนวนเต็ม mat[][] งานของเราคือพิมพ์ prefix sum matrix ของ mat

Prefix sum matrix: ทุกองค์ประกอบของเมทริกซ์คือผลรวมขององค์ประกอบด้านบนและด้านซ้ายของมัน คือ

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

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา

Input: arr =[
    [4  6  1]
    [5  7  2]
    [3  8  9] ]
Output:[
    [4  10  11]
    [9  22  25]
    [12  33  45] ]

ในการแก้ปัญหานี้ วิธีแก้ปัญหาง่ายหนึ่งคือการหา prefixSum โดยการเดินทางผ่านองค์ประกอบทั้งหมดจนถึงตำแหน่ง i,j และบวกพวกเขา แต่มีความซับซ้อนนิดหน่อยสำหรับระบบ

วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าจะเป็นการใช้สูตรสำหรับหาค่าขององค์ประกอบของ prefixSum matrix

สูตรทั่วไปสำหรับองค์ประกอบที่ตำแหน่ง ij คือ

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

กรณีพิเศษบางกรณีคือ

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

โค้ดแสดงการนำวิธีแก้ปัญหาของเราไปใช้

ตัวอย่างโค้ด

#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<<"The prefix Sum Matrix is :\n";
    printPrefixSum(mat);
    return 0;
}

ผลลัพธ์

The prefix Sum Matrix is :
1   3   6
5   12  21
12  27  45