Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <fenwick.h>
Public Types | |
typedef size_t | SizeType |
Public Member Functions | |
void | initialize (FenwickDirection type_, size_t size, const ValueType &initial) |
void | update (SizeType pos, ValueType value) |
ValueType | get_on_interval (SizeType pos) |
Private Member Functions | |
SizeType | _advance (SizeType pos, FenwickDirection direction) |
SizeType | last_one (SizeType x) |
Private Attributes | |
std::vector< ValueType > | data |
FenwickDirection | type |
General Fenwick interval tree.
can update position pos by applying "Operation" can report an "Operation" over values at interval [0..pos] or [pos..size) (not both at once)
Note: sensible operations are only plus, min, max
typedef size_t interval_trees::fenwick::FenwickTree< ValueType, Operation >::SizeType |
SizeType interval_trees::fenwick::FenwickTree< ValueType, Operation >::_advance | ( | SizeType | pos, |
FenwickDirection | direction | ||
) | [inline, private] |
advance to next position in the structure
ValueType interval_trees::fenwick::FenwickTree< ValueType, Operation >::get_on_interval | ( | SizeType | pos | ) | [inline] |
Return value of operation on interval [0, pos] or [pos, size) depending on the type of a tree
void interval_trees::fenwick::FenwickTree< ValueType, Operation >::initialize | ( | FenwickDirection | type_, |
size_t | size, | ||
const ValueType & | initial | ||
) | [inline] |
Initialize fenwick tree
SizeType interval_trees::fenwick::FenwickTree< ValueType, Operation >::last_one | ( | SizeType | x | ) | [inline, private] |
void interval_trees::fenwick::FenwickTree< ValueType, Operation >::update | ( | SizeType | pos, |
ValueType | value | ||
) | [inline] |
Update value on position by value using operator Operation::operation(old, value);
std::vector<ValueType> interval_trees::fenwick::FenwickTree< ValueType, Operation >::data [private] |
FenwickDirection interval_trees::fenwick::FenwickTree< ValueType, Operation >::type [private] |