Matrix Sum

/*You are given a  matrix. You need to print the sum of all the numbers in the rectangle which has  as the top left corner and  as the bottom right corner.

Input:
First line contains two integers, N and M, number of rows and number of columns in the matrix.
Next N lines contains M space separated integers, elements of the matrix.
Next line contains an integer, Q, number of queries.
Each query contains two space separated integers, X and Y.

Output:
For each query, print the sum of all the numbers in the rectangle which has  as the top left corner and  as the bottom right corner.

Constraints:

 elements of matrix 



SAMPLE INPUT 
3 3
1 2 3
4 5 6
7 8 9
2
3 3
2 3
SAMPLE OUTPUT 
45
21
*/

#include <iostream>
using namespace std;
int sumarr[1001][1001]={0};
int ar[1001][1001];
int findsum(int ar[1001][1001],int X,int Y){
if((X<1)||(Y<1))
return 0;

if(sumarr[X][Y]!=0)
return sumarr[X][Y];
else
sumarr[X][Y]=findsum(ar,X-1,Y)+findsum(ar,X,Y-1)-findsum(ar,X-1,Y-1)+ar[X][Y];
return sumarr[X][Y];
}
int main()
{
int N,M,i,j,no,Q,X,Y,sum;
cin>>N>>M;
for(i=1;i<=N;i++){
for(j=1;j<=M;j++){
cin>>no;
ar[i][j]=no;
}
}
cin>>Q;
while(Q-->0){
cin>>X>>Y;
sum=findsum(ar,X,Y);
cout<<sum<<endl;
}
}