1048. Cube Region Totals
A warehouse is modelled as a block of storage cells, where cube[x][y][z] is the net stock change recorded in the cell at layer x, row y and column z. Each query in boxes is [x1, y1, z1, x2, y2, z2] and describes a sub-block that includes both corner cells.
Return an array where entry i is the sum of all cells inside boxes[i]. Values may be negative and totals can exceed 32 bits, so use 64-bit sums. Preprocess the cube once so that every query is answered in constant time.
Example 1
- Input:
- cube = [[[1,2],[3,4]],[[5,6],[7,8]]]boxes = [[0,0,0,1,1,1],[1,0,1,1,1,1]]
- Output:
- [36,14]
- Explanation:
The whole cube sums to 36, and the second box covers the two cells with values 6 and 8, so its total is 14.
Example 2
- Input:
- cube = [[[5,-2,4]]]boxes = [[0,0,1,0,0,2],[0,0,0,0,0,0]]
- Output:
- [2,5]
- Explanation:
The first box holds -2 and 4 for a total of 2, and the second is the single cell with value 5.
Constraints
1 ≤ X, Y, Z ≤ 12 (cube dimensions)
1 ≤ boxes.length ≤ 300
-108 ≤ cube[x][y][z] ≤ 108
0 ≤ x1 ≤ x2 < X, 0 ≤ y1 ≤ y2 < Y, 0 ≤ z1 ≤ z2 < Z
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(X*Y*Z + boxes)
- Space
- O(X*Y*Z)