peltorator

Дерево Отрезков Деревьев Отрезков

Feb 22nd, 2017
167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. typedef long long integer; // change
  2.  
  3. const integer neutr = 0; // change
  4. const int T = (1 << 5); // change
  5.  
  6. integer op(integer a, integer b) // change
  7. {
  8.     return a + b;
  9. }
  10.  
  11. struct Tree
  12. {
  13.     integer a[T][T]; // change
  14.     int n, m; // change
  15.     integer t[T][T];
  16.  
  17.     void build1(int ind, int pos, int v, int l, int r)
  18.     {
  19.         if (l + 1 == r)
  20.         {
  21.             t[ind][v] = a[pos][l];
  22.             return;
  23.         }
  24.         int mid = (r + l) / 2;
  25.         build1(ind, pos, 2 * v, l, mid);
  26.         build1(ind, pos, 2 * v + 1, mid, r);
  27.         t[ind][v] = op(t[ind][2 * v], t[ind][2 * v + 1]);
  28.     }
  29.  
  30.     void build2(int ind, int v, int l, int r)
  31.     {
  32.         t[ind][v] = op(t[2 * ind][v], t[2 * ind + 1][v]);
  33.         if (l + 1 == r)
  34.             return;
  35.         int mid = (r + l) / 2;
  36.         build2(ind, 2 * v, l, mid);
  37.         build2(ind, 2 * v + 1, mid, r);
  38.     }
  39.  
  40.     void buildall(int v, int l, int r)
  41.     {
  42.         if (l + 1 == r)
  43.         {
  44.             build1(v, l, 1, 0, m);
  45.             return;
  46.         }
  47.         int mid = (r + l) / 2;
  48.         buildall(2 * v, l, mid);
  49.         buildall(2 * v + 1, mid, r);
  50.         build2(v, 1, 0, m);
  51.     }
  52.  
  53.     void build()
  54.     {
  55.         buildall(1, 0, n);
  56.     }
  57.  
  58.     Tree(vector<vector<integer> > v)
  59.     {
  60.         n = v.size();
  61.         m = v[0].size();
  62.         for (int i = 0; i < n; i++)
  63.             for (int j = 0; j < m; j++)
  64.                 a[i][j] = v[i][j];
  65.         build();
  66.     }
  67.  
  68.     integer find1(int ind, int v, int ql, int qr, int l, int r) // [ql; qr) - where want to find. [l; r) - current interv
  69.     {
  70.         if (ql >= r || l >= qr)
  71.             return neutr;
  72.         if (ql <= l && r <= qr)
  73.             return t[ind][v];
  74.         int mid = (r + l) / 2;
  75.         return op(find1(ind, 2 * v, ql, qr, l, mid), find1(ind, 2 * v + 1, ql, qr, mid, r));
  76.     }
  77.  
  78.     integer find(int v, int lx, int rx, int ly, int ry, int l, int r) // [lx; rx) x [ly; ry) - where want to find. [l; r) - current interv
  79.     {
  80.         if (lx >= r || l >= rx)
  81.             return neutr;
  82.         if (lx <= l && r <= rx)
  83.             return find1(v, 1, ly, ry, 0, m);
  84.         int mid = (r + l) / 2;
  85.         return op(find(2 * v, lx, rx, ly, ry, l, mid), find(2 * v + 1, lx, rx, ly, ry, mid, r));
  86.     }
  87.  
  88.     integer find(int lx, int rx, int ly, int ry) // find op on [lx; rx) x [ly; ry)
  89.     {
  90.         return find(1, lx, rx, ly, ry, 0, n);
  91.     }
  92. };
RAW Paste Data