fenwick tree 2D

ソースコード

 1#include <iostream>
 2#include <vector>
 3#include <cassert>
 4using namespace std;
 5
 6// FenwickTree2D
 7namespace titan23 {
 8
 9    template<typename T>
10    struct FenwickTree2D {
11        long long _h, _w;
12        vector<T> _bit;
13
14        FenwickTree2D() {}
15        FenwickTree2D(int h, int w) : _h(h+1), _w(w+1), _bit(_h*_w, 0) {
16            assert(_h * _w < 1e9);
17        }
18
19        void add(int h, int w, T x) {
20            assert(0 <= h && h < _h);
21            assert(0 <= w && w < _w);
22            ++h; ++w;
23            while (h < _h) {
24                int j = w;
25                while (j < _w) {
26                    _bit[h*_w+j] += x;
27                    j += (j & (-j));
28                }
29                h += (h & (-h));
30            }
31        }
32
33        void set(int h, int w, T x) {
34            assert(0 <= h && h < _h);
35            assert(0 <= w && w < _w);
36            add(h, w, x - get(h, w));
37        }
38
39        T sum(int h, int w) const {
40            assert(0 <= h && h < _h);
41            assert(0 <= w && w < _w);
42            T res = 0;
43            while (h > 0) {
44                int j = w;
45                while (j > 0) {
46                    res += _bit[h*_w + j];
47                    j -= (j & (-j));
48                }
49                h -= (h & (-h));
50            }
51            return res;
52        }
53
54        T sum(int h1, int w1, int h2, int w2) const {
55            assert(0 <= h1 && h1 <= h2 && h2 <= _h);
56            assert(0 <= w1 && w1 <= w2 && w2 <= _w);
57            return sum(h2, w2) - sum(h2, w1) - sum(h1, w2) + sum(h1, w1);
58        }
59
60        T get(int h, int w) const {
61            assert(0 <= h && h < _h);
62            assert(0 <= w && w < _w);
63            return sum(h, w, h+1, w+1);
64        }
65
66        void print() const {
67            cout << "[" << endl;
68            for (int i = 0; i < _h-1; ++i) {
69                cout << "  ";
70                for (int j = 0; j < _w-1; ++j) {
71                    cout << get(i, j) << " ";
72                }
73                cout << endl;
74            }
75            cout << "]" << endl;
76        }
77    };
78}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/fenwick_tree_2D.cpp