fenwick_tree.cpp File Reference

Fenwick tree. More...

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for fenwick_tree.cpp:

Classes
class	FenwickTree

Functions
int	main ()

Detailed Description

Fenwick tree.

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Function Documentation

main()

int main

(

void

)

Main function

           {
    int n = 5;
    std::vector<int> arr = {1, 2, 3, 4, 5};
    FenwickTree fenwick_tree(arr);
 
    assert(fenwick_tree.sum_range(0, 0) == 1);
    assert(fenwick_tree.sum_range(0, 1) == 3);
    assert(fenwick_tree.sum_range(0, 2) == 6);
    fenwick_tree.update(0, 6);
    assert(fenwick_tree.sum_range(0, 0) == 6);
    assert(fenwick_tree.sum_range(0, 1) == 8);
    assert(fenwick_tree.sum_range(0, 2) == 11);
    return 0;
}

Here is the call graph for this function: