Problem in Solution

#1


What is problem in thi solution

#2

Your code seems little complicated. It can be solved with 3-D fenwick tree.
I will give you the intution then you can try.
Given an array(let say A) of size n initialized to zero. In this array only two operations can be performed

Operations ->
1- > update x
2 -> summation i j
using fenwick tree both of these operation be done in O(logn) time.

First we have to construct a new array(let say B). B[i] stores summation of values of A[x] to A[i](here x is some index less than i). Now to get “summation x y” we have to calculate A[0]+…+A[j] and A[0]+…+A[i].

To get A[0]+…+A[j] we will make use of array B.

sum = 0;
while(j>0) {
sum += B[j];
j -= (j & -j); // consider updated j as x in above explanation.
}

This while loops takes O(logn) time. Similarly we can perform update operation.

In original problem we have to find summation in 3-dimensions. So we can again use fenwick tree with three dimension. Now summation operation will look like this:

long long y1,x1,sum=0;
while (z>0) {
    x1=x;
    while(x1>0) {
        y1=y;
        while(y1>0) {
            sum += matrix[x1][y1][z];
            y1-= (y1 & -y1);   
        }
        x1 -= (x1 & -x1);
    }
    z -= (z & -z);

}
return sum;

Now Time Complexity of update and summation operation will be O((logn)^3). Since we have to reduce each x,y,z coordinate.