Sparse Table 2D
コードについての説明
2 次元静的 RMQ(更新のない $2$ 次元矩形領域最小値クエリ) に $\O (1)$ で答えるデータ構造を $\O (n^2 \log^2 n)$ 時間で構築するアルゴリズム.
$1$ 次元の場合 を拡張し, 各座標 $(i, j)$ および $0 \le k, l \le \lfloor \log_2 n \rfloor$ について $(i, j)$, $(i + 2^k, j)$, $(i, j + 2^l)$, $(i + 2^k, j + 2^l)$ の
$4$ 点からなる矩形領域内の最小値を前計算して保持しておくことで各矩形領域クエリを前計算した $4$ つの矩形領域の $\min$ として $\O (1)$ 時間で答えることが可能になる.
(関数)
query$(lx, ly, rx, ry)$ : $[lx,rx) \times [ly,ry)$ で表される矩形領域の最小値を返す
($n \times n$ 正方領域について)
時間計算量: 前処理 $\O(n^2 \log^2 n)$, クエリ $\O (1)$
空間計算量: $\O(n^2 \log^2 n)$
コード
template<typename T> class SparseTable_2D {
private:
const int R, C;
vector<int> LogTable;
T**** Table;
public:
SparseTable_2D(const vector<vector<T> >& v) : R((int)v.size()), C((int)v[0].size()), LogTable(max(R, C) + 1){
for(int i = 2; i <= max(R, C); ++i){
LogTable[i] = LogTable[i >> 1] + 1;
}
Table = new T***[LogTable[R] + 1];
for(int k = 0; k <= LogTable[R] ; ++k){
Table[k] = new T**[LogTable[C] + 1];
for(int l = 0; l <= LogTable[C]; ++l){
Table[k][l] = new T*[R];
for(int i = 0; i < R; ++i){
Table[k][l][i] = new T[C];
}
}
}
for(int i = 0; i < R; ++i){
for(int j = 0; j < C; ++j){
Table[0][0][i][j] = v[i][j];
}
}
for(int k = 1; (1 << k) <= R; ++k){
for(int i = 0; i + (1 << k) <= R; ++i){
for(int j = 0; j < C; ++j){
Table[k][0][i][j] = min(Table[k - 1][0][i][j], Table[k - 1][0][i + (1 << (k - 1))][j]);
}
}
}
for(int k = 0; (1 << k) <= R; ++k){
for(int l = 1; (1 << l) <= C; ++l){
for(int i = 0; i + (1 << k) <= R; ++i){
for(int j = 0; j + (1 << l) <= C; ++j){
Table[k][l][i][j] = min(Table[k][l - 1][i][j], Table[k][l - 1][i][j + (1 << (l - 1))]);
}
}
}
}
}
~SparseTable_2D(){
for(int i = 0; i <= LogTable[R]; ++i){
for(int j = 0; j <= LogTable[C]; ++j){
for(int k = 0; k < R; ++k){
delete[] Table[i][j][k];
}
delete[] Table[i][j];
}
delete[] Table[i];
}
delete[] Table;
}
T query(const int lx, const int ly, const int rx, const int ry){
const int kx = LogTable[rx - lx];
const int ky = LogTable[ry - ly];
return min({Table[kx][ky][lx][ly], Table[kx][ky][rx - (1 << kx)][ly], Table[kx][ky][lx][ry - (1 << ky)], Table[kx][ky][rx - (1 << kx)][ry - (1 << ky)]});
}
};
verify 用の問題
Codeforces : Animals and Puzzle 提出コード