2次元累積和
(library/dp/cumulative_sum/cumulative_sum_2D.hpp)

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

2次元累積和

できること

• 2次元平面での累積和を返す

計算量

$O(HW)$

使い方

vector<vector<long long>> S = cumulative_sum_2D(G);

$\sum$ (s,t)~(x,y) は以下の包除で求める

long long ans = S[y][x] - S[y][s] - S[t][x] + S[t][s];

Verified with

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

Code

#pragma once
template <typename T>
vector<vector<long long>> cumulative_sum_2D(const vector<T> &G) {
    int H = G.size(), W = G[0].size();
    vector<vector<long long>> S(H + 1, vector<long long>(W + 1));
    for (int i = 0; i < H; ++i) { // 横向き
        for (int j = 0; j < W; ++j) {
            S[i + 1][j + 1] = S[i + 1][j] + G[i][j];
        }
    }
    for (int i = 0; i < H; ++i) { // 縦向き
        for (int j = 0; j < W; ++j) {
            S[i + 1][j + 1] += S[i][j + 1];
        }
    }
    return S;
}

#line 2 "library/dp/cumulative_sum/cumulative_sum_2D.hpp"
template <typename T>
vector<vector<long long>> cumulative_sum_2D(const vector<T> &G) {
    int H = G.size(), W = G[0].size();
    vector<vector<long long>> S(H + 1, vector<long long>(W + 1));
    for (int i = 0; i < H; ++i) { // 横向き
        for (int j = 0; j < W; ++j) {
            S[i + 1][j + 1] = S[i + 1][j] + G[i][j];
        }
    }
    for (int i = 0; i < H; ++i) { // 縦向き
        for (int j = 0; j < W; ++j) {
            S[i + 1][j + 1] += S[i][j + 1];
        }
    }
    return S;
}

Back to top page