2次元累積和

概要

2 次元配列 a から $s[h][w] = \sum_{(i,j) \in [0,h) \times [0,w)} a[i][j]$ となる 2 次元配列 s を作る．これを使うと長方形領域の和が $O(1)$ で計算できる．

使い方

sum(s,i,j,h,w): $\sum_{(i,j) \in [i,i+h) \times [j,j+w)} a[i][j]$ を求める

計算量

構築 $O(hw)$，クエリ $O(1)$

実装

template <class T>
std::vector<std::vector<T>> Imos2D(const std::vector<std::vector<T>>& a) {
    int h = a.size(), w = a[0].size();
    std::vector<std::vector<T>> s(h + 1, std::vector<T>(w + 1, 0));
    rep(i, h) rep(j, w) s[i + 1][j + 1] = a[i][j];
    rep(i, h + 1) rep(j, w) s[i][j + 1] += s[i][j];
    rep(i, h) rep(j, w + 1) s[i + 1][j] += s[i][j];
    return s;
}

template <class T>
int sum(const std::vector<std::vector<T>>& s, int i, int j, int h, int w) {
    return s[i + h][j + w] - s[i][j + w] + s[i][j] - s[i + h][j];
}

検証

たくさん

参考文系

蟻本