I don’t understand 2-d fenwick tree or 1-d fenwick tree completely. Here is code for updating point (x,y) in a matrix.
But what I don’t understand is that it should update whole matrix from (x,y) to (Max_x,Max_y) if I am not wrong. Then when i want sum of matrix (0,0) to (x,y) i use code,
int sum(int x,int y,vector<vector>& v)
{
int ret = 0;
for (int i = x; i >= 0; i = (i&(i+1)) - 1)
{
for(int j=y;j>=0;j = (j&(j+1))-1) ret+=v[i][j];
}
return ret;
}
Now when update matrix at a particular point I just simple use previous function and it is working fine but when I need the sum of particular matrix. I have to use code,
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int s1 = sum(x2,y2,bit);
if(y1>0) s1-=sum(x2,y1-1,bit);
if(x1>0) s1-=sum(x1-1,y2,bit);
if(x1>0&&y1>0) s1+=sum(x1-1,y1-1,bit);
printf("%d\n",s1);
Please tell me what I am missing.