Advertisement
Lhesnor

Untitled

May 18th, 2022
692
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include "iostream"
  2. #include "vector"
  3.  
  4. class FenwickTree {
  5.  private:
  6.   std::vector<std::vector<std::vector<int>>> ft_;
  7.  
  8.  public:
  9.   explicit FenwickTree(int n) {
  10.     ft_.resize(n);
  11.     for (int i = 0; i < n; ++i) {
  12.       ft_[i].resize(n);
  13.       for (int j = 0; j < n; ++j) {
  14.         ft_[i][j].resize(n);
  15.       }
  16.     }
  17.   }
  18.  
  19.   void Increment(int x, int y, int z, int delta) {
  20.     auto n = static_cast<int>(ft_.size());
  21.     for (int i = x; i < n; i = (i | (i + 1))) {
  22.       for (int j = y; j < n; j = (j | (j + 1))) {
  23.         for (int k = z; k < n; k = (k | (k + 1))) {
  24.           ft_[i][j][k] += delta;
  25.         }
  26.       }
  27.     }
  28.   }
  29.  
  30.   int Query(int x, int y, int z) {
  31.     int sum = 0;
  32.     for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
  33.       for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
  34.         for (int k = z; k >= 0; k = (k & (k + 1)) - 1) {
  35.           sum += ft_[i][j][k];
  36.         }
  37.       }
  38.     }
  39.     return sum;
  40.   }
  41.  
  42.   int Sum(int x1, int y1, int z1, int x2, int y2, int z2) {
  43.     return Query(x2, y2, z2) - Query(x1 - 1, y2, z2) - Query(x2, y1 - 1, z2) - Query(x2, y2, z1 - 1) +
  44.            Query(x2, y1 - 1, z1 - 1) + Query(x1 - 1, y2, z1 - 1) + Query(x1 - 1, y1 - 1, z2) -
  45.            Query(x1 - 1, y1 - 1, z1 - 1);
  46.   }
  47. };
  48.  
  49. int main() {
  50.   int n, c = 0;
  51.   std::cin >> n;
  52.   auto tree = FenwickTree(n);
  53.   while (c != 3) {
  54.     int x1, x2, y1, y2, z1, z2;
  55.     int val;
  56.     std::cin >> c;
  57.     if (c == 2) {
  58.       std::cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
  59.       std::cout << tree.Sum(x1, y1, z1, x2, y2, z2) << '\n';
  60.     }
  61.     if (c == 1) {
  62.       std::cin >> x1 >> y1 >> z1 >> val;
  63.       tree.Increment(x1, y1, z1, val);
  64.     }
  65.   }
  66.   return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement