Algoteka
Log in to submit your own samples!

Fenwick Tree

Problem by oml1111
# Tech tags Title Creator Created date
1 0
2022-08-11 08:21
View all samples for this language (1 verified and 0 unverified)

Readable implementation | C++ |

By oml1111 |
0 likes

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

Code

#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
}

Further reading

Data Structures: Fenwick Tree - courses.cs.ut.ee
Fenwick Tree - wikipedia.org

References

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

Problem Description

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.

View sample discussion (0 comments)
View problem discussion (0 comments)