peltorator

2D Sparse Table

Oct 31st, 2018 (edited)
149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int LGN = 10, N = 500, LGM = 10, M = 500;
  2.  
  3. int logs[max(N, M)];
  4. int sparse[LGN][LGM][N][M];
  5.  
  6. int find(int lx, int rx, int ly, int ry)  // [lx; rx) x [ly; ry)
  7. {
  8.     int x = logs[rx - lx], y = logs[ry - ly];
  9.     return max({sparse[x][y][lx][ly], sparse[x][y][rx - (1 << x)][ly],
  10.                 sparse[x][y][lx][ry - (1 << y)], sparse[x][y][rx - (1 << x)][ry - (1 << y)]});
  11. }
  12.  
  13. void buildsparse(vector<vector<int>> &a)
  14. {
  15.     int n = a.size();
  16.     int m = a[0].size();
  17.     for (int i = 2; i < max(n, m); i++) {
  18.         logs[i] = logs[i >> 1] + 1;
  19.     }
  20.     for (int x = 0; x < n; x++) {
  21.         for (int y = 0; y < m; y++) {
  22.             sparse[0][0][x][y] = a[x][y];
  23.         }
  24.     }
  25.     for (int lgx = 0; lgx + 1 < LGN; lgx++) {
  26.         for (int x = 0; x + (1 << lgx) < n; x++) {
  27.             for (int y = 0; y < m; y++) {
  28.                sparse[lgx + 1][0][x][y] = max(sparse[lgx][0][x][y], sparse[lgx][0][x + (1 << lgx)][y]);
  29.             }
  30.         }
  31.     }
  32.     for (int lgx = 0; lgx + 1 < LGN; lgx++) {
  33.         for (int lgy = 0; lgy + 1 < LGM; lgy++) {
  34.             for (int x = 0; x < n; x++) {
  35.                 for (int y = 0; y + (1 << lgy) < m; y++) {
  36.                     sparse[lgx][lgy + 1][x][y] = max(sparse[lgx][lgy][x][y], sparse[lgx][lgy][x][y + (1 << lgy)]);
  37.                 }
  38.             }
  39.         }
  40.     }
  41. }
RAW Paste Data