This documentation is automatically generated by competitive-verifier/competitive-verifier
$2$ 次元配列をもとに $2$ 次元累積和を求める.
sum2d(m)
:$2$ 次元配列 m
をもとに $2$ 次元累積和のテーブルを構築する.get(x, y)
:$(x,y)$ までの累積和を返す.get(sx, sy, tx, ty)
:$(sx,sy)$ から $(tx,ty)$ までの累積和を返す.$sx \leq tx,\ sy \leq ty$ であり,$(sx,sy)$ 側が開区間である.out()
:累積和テーブルを出力する.get()
:$O(1)$out()
:$O(HW)$累積和テーブルを構築する際に,index が1つずれることに注意.(1次元累積和テーブルで table[0]
に $0$ を格納するように,table[0][y]
と table[x][0]
に $0$ を格納している.)
#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#include "../structure/2d_array.cpp"
template<typename T> struct sum2d {
private:
const int H, W;
v2d<T> table;
public:
sum2d(v2d<T> &m) : H(m.size() + 1), W(m[0].size() + 1), table(H, W, 0) {
for(int i = 1; i < H; i++)
for(int j = 1; j < W; j++)
table[i][j] = m[i - 1][j - 1] + table[i][j - 1] + table[i - 1][j] - table[i - 1][j - 1];
}
T get(int x, int y) {
return table[x][y];
}
T get(int sx, int sy, int tx, int ty) {
return table[tx][ty] - table[sx][ty] - table[tx][sy] + table[sx][sy];
}
void out() {
table.out();
}
};
#line 2 "dp/2d_cumulative_sum.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#line 2 "structure/2d_array.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct v2d {
private:
vector<vector<T>> m;
public:
v2d() {}
v2d(int h, int w) : m(h, vector<T>(w)) {}
v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}
void assign(int h, int w) {
m.assign(h, vector<T>(w));
}
void assign(int h, int w, const T init) {
m.assign(h, vector<T>(w, init));
}
inline int size() const {
return m.size();
}
void in() {
for(vector<T> &v : m)
for(T &val : v) cin >> val;
}
void in(int h, int w) {
m.resize(h, vector<T>(w));
in();
}
void out() {
int h = m.size();
for(vector<T> &v : m) {
int sz = v.size();
for(int j = 0; j < sz; j++) {
cout << v[j] << (j == sz - 1 ? '\n' : ' ');
}
}
cout << flush;
}
inline vector<T> &operator[](int idx) {
assert(0 <= idx && idx < m.size());
return m[idx];
}
bool rangeout(int x, int y) {
if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
return false;
}
};
#line 10 "dp/2d_cumulative_sum.cpp"
template<typename T> struct sum2d {
private:
const int H, W;
v2d<T> table;
public:
sum2d(v2d<T> &m) : H(m.size() + 1), W(m[0].size() + 1), table(H, W, 0) {
for(int i = 1; i < H; i++)
for(int j = 1; j < W; j++)
table[i][j] = m[i - 1][j - 1] + table[i][j - 1] + table[i - 1][j] - table[i - 1][j - 1];
}
T get(int x, int y) {
return table[x][y];
}
T get(int sx, int sy, int tx, int ty) {
return table[tx][ty] - table[sx][ty] - table[tx][sy] + table[sx][sy];
}
void out() {
table.out();
}
};