3D prefix sum - Codeforces

→ Pay attention

Before contest
Codeforces Round 1134 (Div. 4)
5 days
Register now »

→ Streams

ICPC NA North Central and South Division

By ICPCNews

Stream is running

View all →

→ Top rated

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3408
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	132
10	cry	130

View all →

→ Find user

→ Recent actions

Detailed →

nikizakr's blog

3D prefix sum

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

Comments (4)

Show archived | Write comment?

Vshining

9 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