3次元累積和
(library/dp/cumulative_sum/cumulative_sum_3D.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/dp/cumulative_sum/cumulative_sum_3D.hpp"

3次元累積和

できること

• 3次元での累積和を返す

計算量

$O(N^3)$

使い方

vector<vector<vector<long long>>> S = cumulative_sum_3D(A);

包除として

// Lx Ly Lzは0-indexed Rx Ry Rzは1-indexed
// S[Rxyz] - S[Lxyz]
long long ans = S[Rx][Ry][Rz] - S[Lx][Ry][Rz] - S[Rx][Ly][Rz] -
        S[Rx][Ry][Lz] + S[Lx][Ly][Rz] + S[Lx][Ry][Lz] +
        S[Rx][Ly][Lz] - S[Lx][Ly][Lz];

Verified with

• 3次元累積和のテスト (tests/dp.cumulative_sum.cumulative_sum_3D.test.cpp)

Code

#pragma once
template <typename T>
vector<vector<vector<long long>>>
cumulative_sum_3D(const vector<vector<vector<T>>> &A) {
    vector<vector<vector<long long>>> S;
    int szx = A.size(), szy = A[0].size(), szz = A[0][0].size();
    S.resize(szx + 1,
             vector<vector<long long>>(szy + 1, vector<long long>(szz + 1, 0)));
    for (int x = 1; x <= szx; ++x) {
        for (int y = 1; y <= szy; ++y) {
            for (int z = 1; z <= szz; ++z) {
                S[x][y][z] = A[x - 1][y - 1][z - 1] + S[x - 1][y][z] +
                             S[x][y - 1][z] + S[x][y][z - 1] -
                             S[x - 1][y - 1][z] - S[x - 1][y][z - 1] -
                             S[x][y - 1][z - 1] + S[x - 1][y - 1][z - 1];
            }
        }
    }
    return S;
}

#line 2 "library/dp/cumulative_sum/cumulative_sum_3D.hpp"
template <typename T>
vector<vector<vector<long long>>>
cumulative_sum_3D(const vector<vector<vector<T>>> &A) {
    vector<vector<vector<long long>>> S;
    int szx = A.size(), szy = A[0].size(), szz = A[0][0].size();
    S.resize(szx + 1,
             vector<vector<long long>>(szy + 1, vector<long long>(szz + 1, 0)));
    for (int x = 1; x <= szx; ++x) {
        for (int y = 1; y <= szy; ++y) {
            for (int z = 1; z <= szz; ++z) {
                S[x][y][z] = A[x - 1][y - 1][z - 1] + S[x - 1][y][z] +
                             S[x][y - 1][z] + S[x][y][z - 1] -
                             S[x - 1][y - 1][z] - S[x - 1][y][z - 1] -
                             S[x][y - 1][z - 1] + S[x - 1][y - 1][z - 1];
            }
        }
    }
    return S;
}

Back to top page