# Untitled

Nov 21st, 2021
64
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. using std::vector;
5. using std::cin;
6. using std::cout;
7.
8. class Fenwick {
9. public:
10. Fenwick(int n): size_(n) {
11. Vol.resize(size_, vector<vector<long long> >(size_, vector<long long> (size_, 0)));
12. }
13.
14. long long Sum(int left_x, int left_y, int left_z,
15. int right_x, int right_y, int right_z) const;
16. void Update(int index_x, int index_y, int index_z, long long value);
17.
18. private:
19. int size_;
20. vector<vector<vector<long long> > > Vol;
21.
22. long long sum(int x, int y, int z) const;
23. };
24.
25.
26. long long Fenwick::Sum(int left_x, int left_y, int left_z,
27. int right_x, int right_y, int right_z) const {
28. --left_x;
29. --left_y;
30. --left_z;
31. // Для подсчёта нужно воспользоваться
32. // формулой включений и исключений
33. return sum(right_x, right_y, right_z) -
34. sum(right_x, right_y, left_z) -
35. sum(left_x, right_y, right_z) -
36. sum(right_x, left_y, right_z) +
37. sum(left_x, right_y, left_z) +
38. sum(right_x, left_y, left_z) +
39. sum(left_x, left_y, right_z) -
40. sum(left_x, left_y, left_z);
41. }
42.
43. long long Fenwick::sum(int x, int y, int z) const {
44. long long ans = 0;
45. for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
46. for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
47. for (int k = z; k >= 0; k = (k & (k + 1)) - 1) {
48. ans += Vol[i][j][k];
49. }
50. }
51. }
52. return ans;
53. }
54.
55. void Fenwick::Update(int index_x, int index_y, int index_z, long long val) {
56. for (int i = index_x; i < size_; i = i | (i + 1)) {
57. for (int j = index_y; j < size_; j = j | (j + 1)) {
58. for (int k = index_z; k < size_; k = k | (k + 1)) {
59. Vol[i][j][k] += val;
60. }
61. }
62. }
63. }
64.
65.
66. int main() {
67. int n;
68. cin >> n;
69. Fenwick tree(n);
70. int x;
71. while (1) {
72. cin >> x;
73. if (x == 1) {
74. int index_x, index_y, index_z;
75. long long k;
76. cin >> index_x >> index_y >> index_z >> k;
77. tree.Update(index_x, index_y, index_z, k);
78. } else if (x == 2) {
79. int index_lx, index_ly, index_lz, index_rx, index_ry, index_rz;
80. cin >> index_lx >> index_ly >> index_lz >>
81. index_rx >> index_ry >> index_rz;
82. long long res = tree.Sum(index_lx, index_ly, index_lz, index_rx, index_ry, index_rz);
83. cout << res << "\n";
84. } else {
85. return 0;
86. }
87. }
88. }
89.
90.
91.