3D prefix sum - Codeforces

→ Pay attention

Before contest
Educational Codeforces Round 173 (Rated for Div. 2)
34:01:26
Register now »

→ Streams

By aryanc403

Before stream 36:11:25

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

View all →

→ Find user

→ Recent actions

Detailed →

nikizakr's blog

3D prefix sum

By nikizakr, history, 7 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
7 years ago
7

Comments (5)

Show archived | Write comment?

Vshining

7 years ago, # |

← 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