We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Cube Summation
  2. Discussions

Cube Summation

  • dehaka
     + 0 comments

    get ur hands dirty with 3D fenwick tree

    very long algo but this doesnt care about the number of queries, the standard approach that scans the queries so far will time out if the number of queries is too large, but this wall of text 3D fenwick tree method wont

    void update(vector<vector<vector<long>>>& fenwick, int x, int y, int z, long value) {
    while (x < fenwick.size()) {
        int tempY = y;
        while (tempY < fenwick.size()) {
            int tempZ = z;
            while (tempZ < fenwick.size()) {
                fenwick[x][tempY][tempZ] = fenwick[x][tempY][tempZ] + value;
                tempZ = tempZ + (tempZ & -tempZ);
            }
            tempY = tempY + (tempY & -tempY);
        }
        x = x + (x & -x);
    }
}

long access(const vector<vector<vector<long>>>& fenwick, int x, int y, int z) {
    long sum = 0;
    while (x > 0) {
        int tempY = y;
        while (tempY > 0) {
            int tempZ = z;
            while (tempZ > 0) {
                sum = sum + fenwick[x][tempY][tempZ];
                tempZ = tempZ - (tempZ & -tempZ);
            }
            tempY = tempY - (tempY & -tempY);
        }
        x = x - (x & -x);
    }
    return sum;
}

int main()
{
    int T, n, m, x, y, z, x1, y1, z1, x2, y2, z2;
    long W;
    string s;
    cin >> T;
    for (int i=1; i <= T; ++i) {
        cin >> n >> m;
        vector<vector<vector<long>>> block(n+1, vector<vector<long>>(n+1, vector<long>(n+1)));
        vector<vector<vector<long>>> fenwick(n+1, vector<vector<long>>(n+1, vector<long>(n+1)));
        for (int j=1; j <= m; ++j) {
            cin >> s;
            if (s == "UPDATE") {
                cin >> x >> y >> z >> W;
                update(fenwick, x, y, z, W - block[x][y][z]);
                block[x][y][z] = W;
            }
            else if (s == "QUERY") {
                cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
                long long A = access(fenwick, x1-1, y2, z2) + access(fenwick, x2, y1-1, z2) + access(fenwick, x2, y2, z1-1);
                long long B = access(fenwick, x1-1, y1-1, z2) + access(fenwick, x1-1, y2, z1-1) + access(fenwick, x2, y1-1, z1-1);
                cout << access(fenwick, x2, y2, z2) - A + B - access(fenwick, x1-1, y1-1, z1-1) << '\n';
            }
        }
    }
}