3D prefix sum - Codeforces

nikizakr's blog

3D prefix sum

By nikizakr, history, 8 years ago, In English

Hi Codeforces :D I'm looking for some problems about 3D prefix sum can you provide some links thanks a lot

nikizakr
8 years ago
7

Comments (4)

Show archived | Write comment?

Vshining

8 years ago, hide # |

← Rev. 4 →

After writing this comment I realized that your post was asking about problems rather than requesting a tutorial :). I hope someone will find this useful anyway.

Well, I think I could explain it right there. So, for 1D prefix sums you simply do S[i + 1] = S[i] + a[i], nothing special here. For 2D, on the other side, you have to subtract overlapping region: S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j]. For 3D there will be even more overlapping: S[i][j][k] = S[i - 1][j][k] + S[i][j - 1][k] + S[i][j][k - 1] - S[i - 1][j - 1][k] - S[i][j - 1][k - 1] - S[i - 1][j][k - 1] + S[i - 1][j - 1][k - 1] + a[i][j][k]. You can find similarity with inclusion-exclusion formulas. So, with adding new dimensions it becomes more burdensome exponentially. You can check out this code:

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector<vector<vector<int>>> a = {{{1, 0, 1}, {0, 0, 0}, {1, 1, 1}},
                                     {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}},
                                     {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}};
    
    
    vector<vector<vector<int>>> S(4, vector<vector<int>>(4, vector<int>(4)));
    
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                S[i][j][k] = S[i - 1][j][k] + S[i][j - 1][k] + S[i][j][k - 1] 
                           - S[i - 1][j - 1][k] - S[i][j - 1][k - 1] - S[i - 1][j][k - 1] 
                           + S[i - 1][j - 1][k - 1] + a[i - 1][j - 1][k - 1];
    
    
    cout << S[3][3][3] << endl;//Entire matrix
    cout << S[2][3][3] - S[1][3][3] << endl;//Middle 2D plane
    cout << S[2][2][2] - S[1][2][2] - S[2][1][2] - S[2][2][1] 
          + S[1][1][2] + S[2][1][1] + S[1][2][1] - S[1][1][1] << endl;//Middle element (at (2, 2, 2))
    
    return 0;
}

→ Reply