#include
using namespace std;
void prefixSum2D(int a[][100],int n,int m)
{
int sum=0;
int psa[100][100];
psa[0][0] = a[0][0];
// Filling first row(N) and first column(M)
for (int i = 1; i < m; i++)
psa[0][i] = psa[0][i - 1] + a[0][i];
for (int i = 1; i < n; i++)
psa[i][0] = psa[i - 1][0] + a[i][0];
// updating the values in the cells
// as per the general formula
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
// values in the cells of new
// array are updated
psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
- psa[i - 1][j - 1] + a[i][j];
}
// displaying the values of the new array
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << psa[i][j] << " ";
cout << "\n";
}
cout<<endl;
for (int Li = 0; Li < n; Li++)
{
for (int Lj = 0; Lj < m; Lj++)
{
for (int Bi = Li; Bi < n; Bi++)
{
for (int Bj = Lj; Bj < m; Bj++)
{
sum+=psa[Bi][Bj]-psa[Li-1][Bj]-psa[Bj][Lj-1]+psa[Li-1][Bj-1];
}
}
}
}
cout<<sum;
}
int main()
{
int n,m;
cout<<"enter number of rows"<<endl;
cin>>n;
cout<<"enter number of columns"<<endl;
cin>>m;
int a[100][100]={0};
//input
for(int row=0;row<n;row++)
{
for(int col=0;col<m;col++)
{
cout<<"enter element "<<row<<","<<col<<endl;
cin>>a[row][col];
}
}
prefixSum2D(a,n,m);
}