peltorator

Sparse Table

Feb 22nd, 2017
152
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. typedef long long integer; // change
  2.  
  3. const int LG = 20, N = 300007; // change
  4.  
  5. integer op(integer a, integer b) // change
  6. {
  7.     return max(a, b);
  8. }
  9.  
  10. struct Sparse
  11. {
  12.     int logs[N];
  13.     integer bin[LG][N];
  14.     vector<integer> a;
  15.  
  16.     int find(int l, int r)  // [l;r)
  17.     {
  18.         int x = logs[r - l];
  19.         return op(bin[x][l], bin[x][r - (1 << x)]);
  20.     }
  21.  
  22.     void buildBin()
  23.     {
  24.         int n = a.size();
  25.         int cur = 0, x = 1;
  26.         for (int i = 0; i < n + 2; i++)
  27.         {
  28.             if (2 * x == i)
  29.             {
  30.                 x *= 2;
  31.                 cur++;
  32.             }
  33.             logs[i] = cur;
  34.         }
  35.         for (int i = 0; i < n; i++)
  36.             bin[0][i] = a[i];
  37.         for (int i = 0; i + 1 < LG; i++)
  38.             for (int j = 0; j < n; j++)
  39.                 bin[i + 1][j] = op(bin[i][j], bin[i][min(j + (1 << i), n - 1)]);
  40.     }
  41.  
  42.     Sparce(vector<integer> b)
  43.     {
  44.         a = b;
  45.         buildBin();
  46.     }
  47. };
RAW Paste Data