CompetitiveProgrammingLibrary/RectangleSum.cpp at master · Koki-Yamaguchi/CompetitiveProgrammingLibrary · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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];
                        }
                }
        }
};