From 2c24b07ac65bfee2a1c41ead0bbc13c0730517ac Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 8 Sep 2020 16:42:40 -0500 Subject: Update fenwick_tree.cpp --- Data Structures/fenwick_tree.cpp | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/Data Structures/fenwick_tree.cpp b/Data Structures/fenwick_tree.cpp index ba75c58..4f73507 100644 --- a/Data Structures/fenwick_tree.cpp +++ b/Data Structures/fenwick_tree.cpp @@ -1,8 +1,9 @@ template class fenwick_tree { -private: vector FT; +private: int N; T FT[MX]; public: - fenwick_tree(int N) { FT.assign(N + 5, 0); } - void update(int x, T val) { if (++x) for (; x < FT.size(); x += x & -x) FT[x] += val; } - T query(int x) { T ret = 0; if (++x) for (; x; x -= x & -x) ret += FT[x]; return ret; } - T query(int x, int y) { return query(y) - query(x - 1); } -}; \ No newline at end of file + fenwick_tree(int n) { N = n } + fenwick_tree(int n, T A[]) { N = n; memcpy(FT, A, sizeof FT); } + void update(int x, T val) { if (++x) for (; x < N; x += x&-x) FT[x] += val; } + T query(int x) { T ret = 0; if (++x) for (; x; x -= x&-x) ret += FT[x]; return ret; } + T query(int x, int y) { return query(y)-query(x-1); } +}; -- cgit v1.2.3-70-g09d2