Competitive-Programming/Data_Structures/Fenwick_Tree_2D_Range_Update_Range_Query.cpp at main · MohammadMazrouei/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

// Range Update & Range Query, O(log(n)*log(m))
template <typename T>
struct FenwickTree2D {
    int n, m;
    vector<vector<array<T, 2>>> f_mul, f_add;

    FenwickTree2D() : n(0), m(0) {}
    FenwickTree2D(int _n, int _m) : n(_n), m(_m) {
        f_mul.assign(n, vector<array<T, 2>>(m, {T{}, T{}}));
        f_add.assign(n, vector<array<T, 2>>(m, {T{}, T{}}));
    }
    // O(n*m) Construction
    FenwickTree2D(const vector<vector<T>>& v) {
        n = v.size();
        m = v[0].size();
        f_mul.assign(n, vector<array<T, 2>>(m, {T{}, T{}}));
        f_add.assign(n, vector<array<T, 2>>(m, {T{}, T{}}));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f_add[i][j][1] = v[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            int r = i | (i + 1);
            if (r < n) {
                for (int j = 0; j < m; j++) {
                    f_add[r][j][1] += f_add[i][j][1];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int r = j | (j + 1);
                if (r < m) {
                    f_add[i][r][1] += f_add[i][j][1];
                }
            }
        }
    }

    void add_y(int x, int y, T mul, T add, vector<vector<array<T, 2>>>& f) {
        for (int i = x; i < n; i = i | (i + 1)) {
            for (int j = y; j < m; j = j | (j + 1)) {
                f[i][j][0] += mul;
                f[i][j][1] += add;
            }
        }
    }
    void add_x(int x, int l2, int r2, T mul, T add) {
        add_y(x, l2, mul, -mul * (l2 - 1), f_mul);
        add_y(x, r2, -mul, mul * r2, f_mul);
        add_y(x, l2, add, -add * (l2 - 1), f_add);
        add_y(x, r2, -add, add * r2, f_add);
    }
    void add(int l1, int r1, int l2, int r2, const T& v) {
        assert(l1 >= 0 && l1 <= r1 && r1 < n);
        assert(l2 >= 0 && l2 <= r2 && r2 < m);
        add_x(l1, l2, r2, v, -v * (l1 - 1));
        add_x(r1, l2, r2, -v, v * r1);
    }
    T get_y(int x, int y, const vector<vector<array<T, 2>>>& f) const {
        T mul{}, add{};
        for (int i = y; i >= 0; i = (i & (i + 1)) - 1) {
            mul += f[x][i][0];
            add += f[x][i][1];
        }
        return mul * y + add;
    }
    T get_x(int x, int y) const {
        T mul{}, add{};
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
            mul += get_y(i, y, f_mul);
            add += get_y(i, y, f_add);
        }
        return mul * x + add;
    }
    T get(int l1, int r1, int l2, int r2) const {
        assert(l1 >= 0 && l1 <= r1 && r1 < n);
        assert(l2 >= 0 && l2 <= r2 && r2 < m);
        l1--, l2--;
        return get_x(r1, r2) - get_x(l1, r2) - get_x(r1, l2) + get_x(l1, l2);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    vector a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    FenwickTree2D<int> fen(a);
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l1, r1, l2, r2, v;
            cin >> l1 >> r1 >> l2 >> r2 >> v;
            l1--, r1--, l2--, r2--;
            fen.add(l1, r1, l2, r2, v);
        } else if (op == 2) {
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;
            l1--, r1--, l2--, r2--;
            cout << fen.get(l1, r1, l2, r2) << '\n';
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}