# IOI '01 P1 - Mobile Phones

Jul 16th, 2022
1,186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. using namespace std;
5.
6. // 2D Fenwick Tree
7. void update(vector<vector<int>> &fenwick, int x, int y, int val) {
8.     for (; x < (int)fenwick.size(); x += x & -x) {
9.         for (int yy=y; yy < (int)fenwick[0].size(); yy += yy & -yy) {
10.             fenwick[x][yy] += val;
11.         }
12.     }
13. }
14.
15. int getSum(vector<vector<int>> &fenwick, int x, int y) {
16.     int sum = 0;
17.     for (; x; x -= x & -x) {
18.         for (int yy = y; yy; yy -= yy & -yy) {
19.             sum += fenwick[x][yy];
20.         }
21.     }
22.     return sum;
23. }
24.
25. inline int rangeSum(vector<vector<int>> &fenwick, int x1, int x2, int y1, int y2) {
26.     return getSum(fenwick, x2, y2) - getSum(fenwick, x1-1, y2)
27.     - getSum(fenwick, x2, y1-1) + getSum(fenwick, x1-1, y1-1);
28. }
29.
30. int main() {
31.     int t, n;
32.     cin >> t >> n;
33.     vector<vector<int>> fenwick(1+n, vector<int>(1+n));
34.     while (cin >> t && t != 3) {
35.         if (t == 1) {
36.             int x, y, a; cin >> x >> y >> a;
37.             update(fenwick, x+1, y+1, a);
38.         } else {
39.             int l, d, r, u; cin >> l >> d >> r >> u;
40.             cout << rangeSum(fenwick, l+1, r+1, d+1, u+1) << endl;
41.         }
42.     }
43.     return 0;
44. }