fenwick_tree.cpp File Reference

Fenwick Tree algorithm implementation More...

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

Include dependency graph for fenwick_tree.cpp:

Go to the source code of this file.

Classes
class	range_queries::fenwick_tree
	The class that initializes the Fenwick Tree. More...

Namespaces
namespace	range_queries
	for std::vector

Functions
static void	tests ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Fenwick Tree algorithm implementation

From Wikipedia, the free encyclopedia.

A Fenwick tree or binary indexed tree (BIT) is a clever implementation of a datastructure called bionomal tree. It can update values and solve range queries with operations that is; commulative, associative and has an inverse for this type of element. It can also solve immutable range queries (min/max), when operations only are associative over this type of element. Some of these restrictions can be removed, by storing redunant information; like in max/min range queries.

Author

Mateusz Grzegorzek

David Leal

Definition in file fenwick_tree.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 132 of file fenwick_tree.cpp.

           {
    tests();  // run self-test implementations
    return 0;
}

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

Definition at line 114 of file fenwick_tree.cpp.

                    {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    range_queries::fenwick_tree 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);
    assert(fenwick_tree.sum_range(0, 3) == 10);
    assert(fenwick_tree.sum_range(0, 4) == 15);
 
    fenwick_tree.update(0, 6);
    std::cout << "All tests have successfully passed!\n";
}