## Algorithm

Problem Name: Data Structures - Cube Summation

In this HackerRank in Data Structures - Cube Summation solutions

Define a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinates (1,1,1) and the last block is defined by the coordinates (n,n,n). There are two types of queries.

``````UPDATE x y z W
``````

Update the value of block (x,y,z) to W.

``````QUERY x1 y1 z1 x2 y2 z2
``````

Calculate the sum of the values 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).

Function Description

Complete the cubeSum function in the editor below.

cubeSum has the following parameters: - *int n: the dimensions of the 3-d matrix - string operations[m]: the operations to perform

Returns
- int[]: the results of each `QUERY` operation

Input Format
The first line contains an integer T , the number of test-cases. T testcases follow.

For each test case, the first line contains two space-separated integers, n and m n the n * n * n matrix.

m defines the number of operations.

The next m lines will contain an operation either of these forms:

`````` 1. UPDATE x y z W
2. QUERY  x1 y1 z1 x2 y2 z2
``````

Sample Input

```2 4 5 UPDATE 2 2 2 4 QUERY 1 1 1 3 3 3 UPDATE 1 1 1 23 QUERY 2 2 2 4 4 4 QUERY 1 1 1 3 3 3 2 4 UPDATE 2 2 2 1 QUERY 1 1 1 1 1 1 QUERY 1 1 1 2 2 2 QUERY 2 2 2 2 2 2 ```

Sample Output

```4 4 27 0 1 1 ```

Explanation
In the first test case, there is a cube of 4 * 4 * 4 and there are 5 queries. Initially all the cells (1,1,1) to (4,4,4) are 0.
`UPDATE 2 2 2 4` makes the cell (2,2,2) = 4
`QUERY 1 1 1 3 3 3`. As (2,2,2) is updated to 4 and the rest are all 0. The answer to this query is 4.
`UPDATE 1 1 1 23`. updates the cell (1,1,1) to 23. `QUERY 2 2 2 4 4 4`. Only the cell (1,1,1) and (2,2,2) are non-zero and (1,1,1) is not between (2,2,2) and (4,4,4). So, the answer is 4.
`QUERY 1 1 1 3 3 3`. 2 cells are non-zero and their sum is 23+4 = 27.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct s_elem
{
int x;
int y;
int z;
long long int value;
struct s_elem *next;
} elem;

int place_value(elem *root, int x, int y, int z, long long int value)
{
while (root != NULL)
{
if (root -> x == x && root -> y == y && root -> z == z)
{
root->value = value;
return 1;
}
root = root->next;
}
return 0;
}

void add_elem(elem **root, int x, int y, int z, long long int value)
{
elem *newelem = (elem *) malloc(sizeof(elem));
newelem->x = x;
newelem->y = y;
newelem->z = z;
newelem->value = value;
newelem->next = *root;
*root = newelem;
}

long long int sum_list(elem *root, int x1, int y1, int z1, int x2, int y2, int z2)
{
long long int sum = 0;
while (root != NULL)
{
if (root->x >= x1 && root->x  < = x2 && root->y >= y1 && root->y <= y2 && root->z >= z1 && root->z <= z2)
sum += root->value;
root = root->next;
}
return sum;
}

void free_list(elem **root)
{
elem *tmp, *current = *root;
while (current != NULL)
{
tmp = current->next;
free(current);
current = tmp;
}
*root = NULL;
}

int main()
{
int test, i, j, size, query;
int x, y, z, x1, y1, z1, x2, y2, z2;
long long int value;
elem *list = NULL;
char *str = malloc(sizeof(char) * 10);
scanf("%d", &test);
for (i = 0; i  <  test; i++)
{
scanf("%d%d", &size, &query);
for (j = 0; j  <  query; j++)
{
scanf("%s", str);
if (str[0] == 'U')
{
scanf("%d%d%d%lld", &x, &y, &z, &value);
if (!place_value(list, x, y, z, value))
{
}
}
else
{
scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
printf("%lld\n", sum_list(list, x1, y1, z1, x2, y2, z2));
}
}
free_list(&list);
}
return 0;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 110;

int T, N, M, X1, Y1, Z1, X2, Y2, Z2, Val[NMAX][NMAX][NMAX];
long long Aib[NMAX][NMAX][NMAX];
char Type[20];

int LSB(int X)
{
return (X & (X - 1)) ^ X;
}

void Update(int X, int Y, int Z, int Val)
{
for(int i = Y; i  < = N; i += LSB(i))
for(int j = Z; j  < = N; j += LSB(j))
Aib[X][i][j] += Val;
}

long long Query(int X, int Y, int Z)
{
long long Now = 0;
for(int i = Y; i; i -= LSB(i))
for(int j = Z; j; j -= LSB(j))
Now += Aib[X][i][j];
return Now;
}

long long Sum(int X1, int Y1, int Z1, int X2, int Y2, int Z2)
{
long long Ans = 0;
for(int i = X1; i  < = X2; ++ i)
Ans += (Query(i, Y2, Z2) - Query(i, Y1 - 1, Z2) - Query(i, Y2, Z1 - 1) + Query(i, Y1 - 1, Z1 - 1));
return Ans;
}

int main()
{
cin >> T;

for(; T; T --)
{
for(int i = 1; i  < = N; ++ i)
for(int j = 1; j  < = N; ++ j)
for(int k = 1; k  < = N; ++ k)
Aib[i][j][k] = Val[i][j][k] = 0;

cin >> N >> M;
for(int i = 1; i  < = M; ++ i)
{
cin >> Type;
if(Type[0] == 'U')
{
int W;
cin >> X1 >> Y1 >> Z1 >> W;
Update(X1, Y1, Z1, -Val[X1][Y1][Z1]);
Update(X1, Y1, Z1, W);
Val[X1][Y1][Z1] = W;
}else
{
cin >> X1 >> Y1 >> Z1 >> X2 >> Y2 >> Z2;
cout << Sum(X1, Y1, Z1, X2, Y2, Z2) << "\n";
}
}
}
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {
public static void update(int[][][]cube, int x,int y, int z, int W) {
cube[x-1][y-1][z-1] = W;
}
public static long query(int[][][] cube, int x1, int y1, int z1, int x2, int y2, int z2) {
long total = 0L;
if (x1>x2) {
int temp = x1;
x1 = x2;
x2 = temp;
}
if (y1>y2) {
int temp = y1;
y1 = y2;
y2 = temp;
}
if (z1>z2) {
int temp = z1;
z1 = z2;
z2 = temp;
}
for (int i = x1; i  < = x2; i++) {
for (int j = y1; j  < = y2; j++) {
for (int k = z1; k  < = z2; k++) {
long temp = (long)cube[i-1][j-1][k-1];
total+=temp;
}
}
}
}
public static void main(String[] args) {
Scanner inp = new Scanner(System.in);
int T = inp.nextInt();
for (int i = 0; i  <  T; i++) {
int N = inp.nextInt();
int M = inp.nextInt();
int [][][] cube = new int [N][N][N];
for (int j = 0; j  <  M; j++) {
String op = inp.next();
if (op.equals("UPDATE")) {
update(cube,inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt());
} else {
System.out.println(query(cube,inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt(),inp.nextInt()));
}
}
}
}
}
``````
Copy The Code &

### #5 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});

process.stdin.on('end', function() {
inputString = inputString.split('\n');

main();
});

return inputString[currentLine++];
}

/*
* Complete the 'cubeSum' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
*  1. INTEGER n
*  2. STRING_ARRAY operations
*/

function cubeSum(n, operations) {
// sparse matrix? + hash + bloomFilter
let i = -1;
const map = new Map();
const queries = [];
while (++i  <  operations.length) {
const op = operations[i].split(' ');
const name = op[0];
switch (name) {
case 'UPDATE':
const [_u, x, y, z, w] = op.map(a => +a);
const key = `\${x}_\${y}_\${z}`;
map.set(key, w);
break;
case 'QUERY':
const [_q, x1, y1, z1, x2, y2, z2] = op.map(a => +a);
let sum = 0
for (const pair of map) {
const [key, value] = pair;
const [x,y,z] = key.split('_').map(a => +a);

if (
x >= x1 && x  < = x2 &&
y >= y1 && y <= y2 &&
z >= z1 && z <= z2
) {
sum += value;
}
}

queries.push(sum);
break;
default:
return;
}
}
return queries;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

for (let TItr = 0; TItr  <  T; TItr++) {
const firstMultipleInput = readLine().replace(/\s+\$/g, '').split(' ');

const matSize = parseInt(firstMultipleInput[0], 10);

const m = parseInt(firstMultipleInput[1], 10);

let ops = [];

for (let i = 0; i  <  m; i++) {
ops.push(opsItem);
}

const res = cubeSum(matSize, ops);

ws.write(res.join('\n') + '\n');
}

ws.end();
}

``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
import os
import sys

def cubeSum(cmds):
cube={}
for i in cmds:
if(i[0]=="UPDATE"):
x=cube.get(i[1], dict())
y=x.get(i[2], dict())
y[i[3]]=i[4]
x[i[2]]=y
cube[i[1]]=x
else:
sums=0
for j in cube:
if(j>=i[1] and j<=i[4]>:
for k in cube[j]:
if(k>=i[2] and k<=i[5]>:
for l in cube[j][k]:
if(l>=i[3] and l<=i[6]):
sums+=cube[j][k][l]
print(sums)

if __name__ == '__main__':
tests=int(input())
for i in range(tests):
[N, M]=[int(var) for var in input().split()]
cmds=[]
for j in range(M):
ip=input().split()
for k in range(1, len(ip)):
ip[k]=int(ip[k])
cmds.append(ip)
cubeSum(cmds>
``````
Copy The Code &