diff options
author | Ta180m | 2020-06-26 11:51:11 -0500 |
---|---|---|
committer | Ta180m | 2020-06-26 11:51:11 -0500 |
commit | 28aa8c28f6530f0f917736de4495e539d3138d66 (patch) | |
tree | da1204952aea198db39ca360eb4968e819b69472 | |
parent | d9d672e7aeeffb6bc582047c154b23f1e7176e6d (diff) |
Update fenwick_tree_2d.cpp
-rw-r--r-- | Data Structures/fenwick_tree_2d.cpp | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/Data Structures/fenwick_tree_2d.cpp b/Data Structures/fenwick_tree_2d.cpp index 64d1a78..f4aa522 100644 --- a/Data Structures/fenwick_tree_2d.cpp +++ b/Data Structures/fenwick_tree_2d.cpp @@ -1,24 +1,24 @@ -class fenwick_tree_2d { -private: int N, M; vector<vector<int>> FT; +template<typename T> class fenwick_tree_2d { +private: int N, M; vector<vector<T>> FT; public: fenwick_tree_2d(int n, int m) { N = n + 1, M = m + 1; FT.resize(N); for (int i = 0; i < N; i++) FT[i].resize(M, 0); } - void update(int x, int y, int val) { + void update(int x, int y, T val) { for (int i = x; i < N; i += i & -i) { for (int j = y; j < M; j += j & -j) FT[i][j] += val; } } - int query(int x, int y) { - int ret = 0; + T query(int x, int y) { + T ret = 0; for (int i = x; i > 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) ret += FT[i][j]; } return ret; } - int query(int xl, int xr, int yl, int yr) { + T query(int xl, int xr, int yl, int yr) { return query(xr, yr) - query(xl - 1, yr) - query(xr, yl - 1) + query(xl - 1, yl - 1); } };
\ No newline at end of file |