Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Sparse Table 2D

コードについての説明

2 次元静的 RMQ(更新のない 2 次元矩形領域最小値クエリ) に O(1) で答えるデータ構造を O(n2log2n) 時間で構築するアルゴリズム.
1 次元の場合 を拡張し, 各座標 (i,j) および 0≤k,l≤⌊log2n⌋ について (i,j), (i+2k,j), (i,j+2l), (i+2k,j+2l) の 4 点からなる矩形領域内の最小値を前計算して保持しておくことで各矩形領域クエリを前計算した 4 つの矩形領域の min として O(1) 時間で答えることが可能になる.

(関数)
query(lx,ly,rx,ry) : [lx,rx)×[ly,ry) で表される矩形領域の最小値を返す

(n×n 正方領域について)
時間計算量: 前処理 O(n2log2n), クエリ O(1)
空間計算量: O(n2log2n)

コード

  1. template<typename T> class SparseTable_2D {
  2. private:
  3.     const int R, C;
  4.     vector<int> LogTable;
  5.     T**** Table;
  6. public:
  7.     SparseTable_2D(const vector<vector<T> >& v) : R((int)v.size()), C((int)v[0].size()), LogTable(max(R, C) + 1){
  8.         for(int i = 2; i <= max(R, C); ++i){
  9.             LogTable[i] = LogTable[i >> 1] + 1;
  10.         }
  11.         Table = new T***[LogTable[R] + 1];
  12.         for(int k = 0; k <= LogTable[R] ; ++k){
  13.             Table[k] = new T**[LogTable[C] + 1];
  14.             for(int l = 0; l <= LogTable[C]; ++l){
  15.                 Table[k][l] = new T*[R];
  16.                 for(int i = 0; i < R; ++i){
  17.                     Table[k][l][i] = new T[C];
  18.                 }
  19.             }
  20.         }
  21.         for(int i = 0; i < R; ++i){
  22.             for(int j = 0; j < C; ++j){
  23.                 Table[0][0][i][j] = v[i][j];
  24.             }
  25.         }
  26.         for(int k = 1; (1 << k) <= R; ++k){
  27.             for(int i = 0; i + (1 << k) <= R; ++i){
  28.                 for(int j = 0; j < C; ++j){
  29.                     Table[k][0][i][j] = min(Table[k - 1][0][i][j], Table[k - 1][0][i + (1 << (k - 1))][j]);
  30.                 }
  31.             }
  32.         }
  33.         for(int k = 0; (1 << k) <= R; ++k){
  34.             for(int l = 1; (1 << l) <= C; ++l){
  35.                 for(int i = 0; i + (1 << k) <= R; ++i){
  36.                     for(int j = 0; j + (1 << l) <= C; ++j){
  37.                         Table[k][l][i][j] = min(Table[k][l - 1][i][j], Table[k][l - 1][i][j + (1 << (l - 1))]);
  38.                     }
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     ~SparseTable_2D(){
  44.         for(int i = 0; i <= LogTable[R]; ++i){
  45.             for(int j = 0; j <= LogTable[C]; ++j){
  46.                 for(int k = 0; k < R; ++k){
  47.                     delete[] Table[i][j][k];
  48.                 }
  49.                 delete[] Table[i][j];
  50.             }
  51.             delete[] Table[i];
  52.         }
  53.         delete[] Table;
  54.     }
  55.     T query(const int lx, const int ly, const int rx, const int ry){
  56.         const int kx = LogTable[rx - lx];
  57.         const int ky = LogTable[ry - ly];
  58.         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)]});
  59.     }
  60. };

verify 用の問題

Codeforces : Animals and Puzzle 提出コード