Came across another interesting problem on hackerrank related to range sum query in 3 dimensions.
The question goes as below -
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries.
UPDATE x y z W
updates the value of block (x,y,z) to W.
QUERY x1 y1 z1 x2 y2 z2
calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive).
We will stick to creating a fenwick tree here in case of a cube although this question has larger implication in the database world for calculating sums and averages and has much better solutions like lazy propagation of segment trees, quad trees and octet trees.
I wont go deeper into explaining fenwick trees/ binary indexed tree as there are many blogs and videos explaining the same but I highly recommend this link to visualize the workings of it for any application. A question arises as to why use Fenwick tree and not segment tree for this question and the general rule of thumb would be its easier to code Fenwick tree and any application that can be solved using that, should make use of fenwick trees as segment trees have a wide range of applications and provide more flexibility in exchange for heavy maintainability of code/application.
The central idea around creation of Fenwick trees is to affect the minimal number of nodes during an update operation and also use minimum while calculating a metric from it. The main gist around doing this is as follows :-
Populating next/child node ->
- 2's complement of current node index
- AND it with current node index
- ADD to current node index
Calculating parent node ->
- 2's complement of current node index
- AND it with current node index
- SUBTRACT it from current node index.
For a range sum query on a two dimensional space from point (1,1) to (3,3), the calculation on the Fenwick tree can be visualized as below :-
 |
| fig 2 : 2D Range sum query |
which can be formulated as -
sum(row2+1, col2+1) - sum(row1, col2+1) - sum(row2+1, col1) + sum(row1,col1) = ∑(row1, col1) to (row2,col2)
Similarly, for a range sum query on a three dimensional space from point (1,1,1) to (4,4,3), the calculation on the Fenwick tree can be visualized as below :-
 |
| fig 3 : 3D Range sum query |
which can be formulated as -
sum(x2+1,y2+1,z2+1) - sum(x1,y1,z1) - sum(x1,y2+1,z2+1) - sum(x2+1,y1,z2+1) - sum(x2+1,y2+1,z1) + sum(x1,y1,z2+1) + sum(x1,y2+1,z1) + sum(x2+1,y1,z1) = ∑(x1, y1, z1) to (x2, y2, z2)
Pasting the solution code in Java below. A minor confusion can be caused when submitting solution to hackerrank as for this problem, the arrays start from 1 instead of 0 and hence an array with n as 3 goes from 1,1,1 to 3,3,3.
import java.io.*;
import java.util.*;
public class Solution {
long[][][] tree;
long[][][] nums;
private int dimensions = 0;
public Solution(int dimensions) {
if (dimensions == 0) return;
this.dimensions = dimensions;
tree = new long[dimensions+1][dimensions+1][dimensions+1];
nums = new long[dimensions][dimensions][dimensions];
}
public void update(int x, int y, int z, int value) {
long delta = value - nums[x][y][z];
nums[x][y][z] = value;
for (int i = x + 1; i <= dimensions; i += i & (-i)) {
for (int j = y + 1; j <= dimensions; j += j & (-j)) {
for (int k = z + 1; k <= dimensions; k += k & (-k)) {
tree[i][j][k] += delta;
}
}
}
}
public void query(int x1, int y1, int z1, int x2, int y2, int z2) {
long result = sum(x2+1,y2+1,z2+1) - sum(x1,y1,z1) - sum(x1,y2+1,z2+1) - sum(x2+1,y1,z2+1) - sum(x2+1,y2+1,z1) + sum(x1,y1,z2+1) + sum(x1,y2+1,z1) + sum(x2+1,y1,z1);
System.out.println(result);
}
public long sum(int x, int y, int z) {
long sum = 0l;
for (int i = x; i > 0; i -= i & (-i)) {
for (int j = y; j > 0; j -= j & (-j)) {
for (int k = z; k > 0; k -= k & (-k)) {
sum += tree[i][j][k];
}
}
}
return sum;
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner ob = new Scanner(System.in);
Solution solution = null;
int testcases = ob.nextInt();
ob.nextLine();
for (int i = 0; i < testcases; i++) {
String numsLine = ob.nextLine();
String[] numsLineParts = numsLine.trim().split(" ");
int dimensions = Integer.valueOf(numsLineParts[0]);
int numOperations = Integer.valueOf(numsLineParts[1]);
solution = new Solution(dimensions);
for (int j = 0; j < numOperations; j++) {
String line = ob.nextLine();
String[] lineParts = line.split(" ");
if (lineParts[0].equals("UPDATE")) {
solution.update(Integer.valueOf(lineParts[1])-1, Integer.valueOf(lineParts[2])-1, Integer.valueOf(lineParts[3])-1, Integer.valueOf(lineParts[4]));
}
if (lineParts[0].equals("QUERY")) {
solution.query(Integer.valueOf(lineParts[1])-1, Integer.valueOf(lineParts[2])-1, Integer.valueOf(lineParts[3])-1, Integer.valueOf(lineParts[4])-1, Integer.valueOf(lineParts[5])-1, Integer.valueOf(lineParts[6])-1);
}
}
}
}
}
The time complexity of this solution is O(log(X) * log(Y) * log(Z)) = O(log(N))3
Posts
![PixBlog 6 - The land of 14ers [Colorado]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgxQmX1nb3_7tvQIoZGYBCk2rWgue68ckjqE421fZ0b2KCPuBzll72x7l_jktk7zukScyrVD-0Ljt4kRRgliTHisgcQVO8SL_Vd_vynHy5fo11Ycjo1YqHMLvOf4TlUzC4f_dbRa4eX239p/s72-c/IMG_5948.JPG)
No Fox too fast, No Fence too high....