二次元累積和のライブラリ

二次元累積和のライブラリです。手で書いた方が早いレベルですが、何も考えずに求めたいときは貼ります。

グリッド上で任意の長方形に含まれる数の総和を $O(HW)$ の初期化の後に $O(1)$ で求めます。

antaさんがこれをRectangleSumと名付けて使っていた気がするので、真似て名付けました。

これなどで $verify$ しています。

区間は閉区間にしていますが、半開区間に変えた方が良い場合もあると思います。

template <typename T>
struct RectangleSum {
        vector<vector<T>> sum;
        T GetSum(int left, int right, int top, int bottom) { //[left, right], [top, bottom]
                T res = sum[bottom][right];
                if (left > 0) res -= sum[bottom][left - 1];
                if (top > 0) res -= sum[top - 1][right];
                if (left > 0 && top > 0) res += sum[top - 1][left - 1];
                return res;
        }
        void init(const vector<vector<T>> &s, int h, int w) {
                sum.resize(h);
                for (int i = 0; i < h; i ++) sum[i].resize(w, 0);
                for (int y = 0; y < h; y ++) {
                        for (int x = 0; x < w; x ++) {
                                sum[y][x] = s[y][x];
                                if (y > 0) sum[y][x] += sum[y - 1][x];
                                if (x > 0) sum[y][x] += sum[y][x - 1];
                                if (y > 0 && x > 0) sum[y][x] -= sum[y - 1][x - 1];
                        }
                }
        }
};