aboutsummaryrefslogtreecommitdiff
path: root/Data Structures/fenwick_tree.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Data Structures/fenwick_tree.cpp')
-rw-r--r--Data Structures/fenwick_tree.cpp13
1 files 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<typename T> class fenwick_tree {
-private: vector<T> 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); }
+};