Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "iostream"
- #include "vector"
- class FenwickTree {
- private:
- std::vector<std::vector<std::vector<int>>> ft_;
- public:
- explicit FenwickTree(int n) {
- ft_.resize(n);
- for (int i = 0; i < n; ++i) {
- ft_[i].resize(n);
- for (int j = 0; j < n; ++j) {
- ft_[i][j].resize(n);
- }
- }
- }
- void Increment(int x, int y, int z, int delta) {
- auto n = static_cast<int>(ft_.size());
- for (int i = x; i < n; i = (i | (i + 1))) {
- for (int j = y; j < n; j = (j | (j + 1))) {
- for (int k = z; k < n; k = (k | (k + 1))) {
- ft_[i][j][k] += delta;
- }
- }
- }
- }
- int Query(int x, int y, int z) {
- int sum = 0;
- for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
- for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
- for (int k = z; k >= 0; k = (k & (k + 1)) - 1) {
- sum += ft_[i][j][k];
- }
- }
- }
- return sum;
- }
- int Sum(int x1, int y1, int z1, int x2, int y2, int z2) {
- return Query(x2, y2, z2) - Query(x1 - 1, y2, z2) - Query(x2, y1 - 1, z2) - Query(x2, y2, z1 - 1) +
- Query(x2, y1 - 1, z1 - 1) + Query(x1 - 1, y2, z1 - 1) + Query(x1 - 1, y1 - 1, z2) -
- Query(x1 - 1, y1 - 1, z1 - 1);
- }
- };
- int main() {
- int n, c = 0;
- std::cin >> n;
- auto tree = FenwickTree(n);
- while (c != 3) {
- int x1, x2, y1, y2, z1, z2;
- int val;
- std::cin >> c;
- if (c == 2) {
- std::cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
- std::cout << tree.Sum(x1, y1, z1, x2, y2, z2) << '\n';
- }
- if (c == 1) {
- std::cin >> x1 >> y1 >> z1 >> val;
- tree.Increment(x1, y1, z1, val);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement