2次元累積和
(datastructure/cumulativesum/cumulativesum2d.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "datastructure/cumulativesum/cumulativesum2d.hpp"

概要

静的な2次元配列に対する矩形和クエリに答える.

計算量

• 構築 : $O(hw)$
• クエリ : $O(1)$

使用例

• CumulativeSum2D<int> acc(v) : vで2次元累積和を構築.
• acc.query(a, b, c, d) : 矩形$[a, b]$から$(c, d)$までのクエリ.

Verified with

• test/yukicoder/755.test.cpp

Code

/**
* @brief 2次元累積和
* @docs docs/datastructure/cumulativesum/cumulativesum2d.md
*/

template <class T>
struct CumulativeSum2D {
    int H, W;
    vector<vector<T>> data;
    CumulativeSum2D(const vector<vector<T>> &v) {
        H = v.size();
        W = (H == 0) ? 0 : v[0].size();
        data.assign(H + 1, vector<T>(W + 1, 0));
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                data[i + 1][j + 1] = v[i][j] + data[i + 1][j] + data[i][j + 1] - data[i][j];
            }
        }
    }
    T query(int sx, int sy, int gx, int gy) {
        return data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy];
    }
};

#line 1 "datastructure/cumulativesum/cumulativesum2d.hpp"
/**
* @brief 2次元累積和
* @docs docs/datastructure/cumulativesum/cumulativesum2d.md
*/

template <class T>
struct CumulativeSum2D {
    int H, W;
    vector<vector<T>> data;
    CumulativeSum2D(const vector<vector<T>> &v) {
        H = v.size();
        W = (H == 0) ? 0 : v[0].size();
        data.assign(H + 1, vector<T>(W + 1, 0));
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                data[i + 1][j + 1] = v[i][j] + data[i + 1][j] + data[i][j + 1] - data[i][j];
            }
        }
    }
    T query(int sx, int sy, int gx, int gy) {
        return data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy];
    }
};

Back to top page