diff options
| -rw-r--r-- | datastructures/fenwickTree.cpp | 11 |
1 files changed, 5 insertions, 6 deletions
diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp index 3b54fc9..cd30329 100644 --- a/datastructures/fenwickTree.cpp +++ b/datastructures/fenwickTree.cpp @@ -1,6 +1,11 @@ vector<int> FT; //Fenwick-Tree int n; +//Adds val to index i. Time Complexity O(log(n)) +void updateFT(int i, int val) { + i++; while(i <= n) { FT[i] += val; i += (i & (-i)); } +} + //Build an Fenwick-Tree over an array a. Time Complexity: O(n*log(n)) void buildFenwickTree(vector<int>& a) { n = a.size(); @@ -14,9 +19,3 @@ int prefix_sum(int i) { while(i > 0) { sum += FT[i]; i -= (i & (-i)); } return sum; } - -//Adds val to index i. Time Complexity O(log(n)) -void updateFT(int i, int val) { - i++; while(i <= n) { FT[i] += val; i += (i & (-i)); } -} - |