| # | Likes | Tech tags | Title | Creator | Created date |
|---|---|---|---|---|---|
| 1 | 0 |
2022-08-11 08:21
|
An array implementation of the Fenwick Tree data structure for calculating prefix sums. Provides \(O(\log n)\) addition to position and \(O(\log n)\) prefix query operations. Indexing of positions starts from 1
#include <vector>
struct FenwickTreeSum { // Prefix sum fenwick tree
std::vector<int> data;
FenwickTreeSum(int nsize) { // Initializes Fenwick Tree covering positions [0, nsize)
data.resize(nsize+1, 0);
}
int get(int pos) { // Returns sum of [0, pos)
int result = 0;
while(!(pos == 0)) {
result += data[pos];
pos -= (pos & -pos);
}
return result;
}
void add(int pos, int to_add) { // Adds to position pos
pos++;
while(!(pos >= (int)data.size())) {
data[pos] += to_add;
pos += (pos & -pos);
}
}
};
int main() {
FenwickTreeSum ftree(10);
ftree.add(5, 15); // Add 15 to position 5
int prefix_sum = ftree.get(6); // Get sum of elements up to index 5
}
| classes | ||
std::vector |
en.cppreference.com | cplusplus.com |
| functions | ||
std::vector::size |
en.cppreference.com | cplusplus.com |
std::vector::vector |
en.cppreference.com | cplusplus.com |
Implement a Fenwick Tree data structure for tracking prefix sums. Add some value to some position in that tree and then fetch the sum of some prefix.