dynamic fenwick tree 2D

ソースコード

 1#include <iostream>
 2#include <vector>
 3#include <unordered_map>
 4#include <map>
 5#include <cassert>
 6using namespace std;
 7
 8#include <ext/pb_ds/assoc_container.hpp>
 9#include <ext/pb_ds/hash_policy.hpp>
10
11// DynamicFenwickTree2D
12namespace titan23 {
13
14  template<typename T, typename W>
15  struct DynamicFenwickTree2D {
16    int _h, _w;
17    unordered_map<T, unordered_map<T, W>> _bit;
18
19    DynamicFenwickTree2D() {}
20    DynamicFenwickTree2D(T h, T w) : _h(h+1), _w(w+1) {}
21
22    void add(T h, T w, W x) {
23      assert(0 <= h && h < _h);
24      assert(0 <= w && w < _w);
25      ++h; ++w;
26      while (h < _h) {
27        T j = w;
28        auto it = _bit.find(h);
29        if (it == _bit.end()) {
30          _bit[h];
31          it = _bit.find(h);
32        }
33        while (j < _w) {
34          it->second[j] += x;
35          j += j & (-j);
36        }
37        h += h & (-h);
38      }
39    }
40
41    void set(int h, int w, T x) {
42      assert(0 <= h && h < _h);
43      assert(0 <= w && w < _w);
44      add(h, w, x - get(h, w));
45    }
46
47    W sum(T h, T w) const {
48      assert(0 <= h && h < _h);
49      assert(0 <= w && w < _w);
50      W res = 0;
51      while (h > 0) {
52        T j = w;
53        auto it_h = _bit.find(h);
54        if (it_h != _bit.end()) {
55          while (j > 0) {
56            auto it_j = it_h->second.find(j);
57            if (it_j != it_h->second.end()) {
58              res += it_j->second;
59            }
60            j -= j & (-j);
61          }
62        }
63        h -= h & (-h);
64      }
65      return res;
66    }
67
68    W sum(T h1, T w1, T h2, T w2) const {
69      assert(0 <= h1 && h1 <= h2 && h2 <= _h);
70      assert(0 <= w1 && w1 <= w2 && w2 <= _w);
71      return sum(h2, w2) - sum(h2, w1) - sum(h1, w2) + sum(h1, w1);
72    }
73
74    W get(T h, T w) {
75      assert(0 <= h && h < _h);
76      assert(0 <= w && w < _w);
77      return sum(h, w, h+1, w+1);
78    }
79
80    void print() {
81    }
82  };
83}  // namespace titan23

仕様

Warning

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