cumulative sum 2D

ソースコード

 1#include <vector>
 2#include <cassert>
 3using namespace std;
 4
 5// CumulativeSum2D
 6namespace titan23 {
 7/**
 8 * @brief 2次元累積和ライブラリ
 9 *
10 * @tparam T
11 */
12template<typename T>
13class CumulativeSum2D {
14  private:
15    int h, w;
16    vector<T> acc;
17
18  public:
19    CumulativeSum2D() {}
20    CumulativeSum2D(int h, int w, const vector<vector<T>> &a, T e) :
21            h(h), w(w), acc((h+1)*(w+1), e) {
22        for (int ij = 0; ij < h*w; ++ij) {
23            int i = ij / w, j = ij % w;
24            acc[(i+1)*(w+1)+j+1] = acc[i*(w+1)+j+1] + acc[(i+1)*(w+1)+j] - acc[i*(w+1)+j] + a[i][j];
25        }
26    }
27
28    //! `[h1, h2) x [w1, w2)` の和を返す / `O(1)`
29    T sum(const int h1, const int w1, const int h2, const int w2) const {
30        assert(0 <= h1 && h1 <= h2 && h2 <= h);
31        assert(0 <= w1 && w1 <= w2 && w2 <= w);
32        return acc[h2*(w+1)+w2] - acc[h2*(w+1)+w1] - acc[h1*(w+1)+w2] + acc[h1*(w+1)+w1];
33    }
34};
35}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/cumulative_sum_2D.cpp