累積和(1D,2D,3D)

1
Cumulate1D c1(vector);
2
Cumulate2D c2(matrix);
3
Cumulate3D c3(tensor);

1
c1.query(x1,x2);
2
c2.query(y1,x1,y2,x2);
3
c3.query(z1,y1,x1,z2,y2,x2);

1
template <class T>
2
class Cumulate1D {
3
  vector<T> sum;
4
public:
5
  Cumulate1D(const vector<T> &_g) : sum(_g.size() + 1) {
6
    for (int i = 0; i < _g.size(); i++)
7
      sum[i + 1] = sum[i] + _g[i];
8
  }
9
  T query(int s, int e) { return sum[e] - sum[s]; };
10
};
11
template <class T>
12
class Cumulate2D {
13
  vector<vector<T>> sum;
14
public:
15
  Cumulate2D(const vector<vector<T>> &_g) : sum(_g.size() + 1, vector<T>(_g[0].size() + 1)) {
16
    for (int y = 0; y < _g.size(); y++)
17
      for (int x = 0; x < _g[0].size(); x++)
18
        sum[y + 1][x + 1] = sum[y][x + 1] + sum[y + 1][x] - sum[y][x] + _g[y][x];
19
  }
20
  T query(int y1, int x1, int y2, int x2) { return sum[y2][x2] - sum[y1][x2] - sum[y2][x1] + sum[y1][x1]; }
21
};
22
template <class T>
23
class Cumulate3D {
24
  vector<vector<vector<T>>> sum;
25
public:
26
  Cumulate3D(const vector<vector<vector<T>>> &_g) : sum(_g.size() + 1, vector<vector<T>>(_g[0].size() + 1, vector<T>(_g[0][0].size() + 1))) {
27
    for (int z = 0; z < _g.size(); z++)
28
      for (int y = 0; y < _g[0].size(); y++)
29
        for (int x = 0; x < _g[0][0].size(); x++)
30
          sum[z + 1][y + 1][x + 1] = _g[z][y][x] + sum[z + 1][y + 1][x] + sum[z + 1][y][x + 1] + sum[z][y + 1][x + 1] - sum[z + 1][y][x] - sum[z][y + 1][x] - sum[z][y][x + 1] + sum[z][y][x];
31
  }
32
  T query(int z1, int y1, int x1, int z2, int y2, int x2) { return sum[z2][y2][x2] - sum[z2][y2][x1] - sum[z2][y1][x2] - sum[z1][y2][x2] + sum[z2][y1][x1] + sum[z1][y2][x1] + sum[z1][y1][x2] - sum[z1][y1][x1]; }
33
};