range_queries::fenwick_tree Class Reference

The class that initializes the Fenwick Tree. More...

Collaboration diagram for range_queries::fenwick_tree:

Public Member Functions
template<typename T >
	fenwick_tree (const std::vector< T > &arr)
	Class Constructor.
template<typename T >
	fenwick_tree (T x)
	Class Constructor.
template<typename T >
void	update (T id, T val)
	Updates the value of an element in original array and accordingly updates the values in BIT array.
template<typename T >
int	sum (T id)
	Returns the sum of elements in range from 0 to ID.
int	sum_range (int l, int r)
	Returns the prefix sum in range from L to R.

Private Member Functions
int	offset (int x)
	Returns the highest power of two which is not more than x.

Private Attributes
size_t	n = 0
	No. of elements present in input array.
std::vector< int >	bit {}
	Array that represents Binary Indexed Tree.

Detailed Description

The class that initializes the Fenwick Tree.

Constructor & Destructor Documentation

fenwick_tree() [1/2]

template<typename T >

range_queries::fenwick_tree::fenwick_tree ( const std::vector< T > & arr )

inlineexplicit

Class Constructor.

Template Parameters

T	the type of the array

Parameters

[in]

arr

Input array for which prefix sum is evaluated.

Returns

void

                                                   : n(arr.size()) {
        bit.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            update(i, arr[i]);
        }
    }

Here is the call graph for this function:

fenwick_tree() [2/2]

template<typename T >

range_queries::fenwick_tree::fenwick_tree ( T x )

inlineexplicit

Class Constructor.

Template Parameters

T	the type of the variable

Parameters

[in]

x

Size of array that represents Binary Indexed Tree.

Returns

void

: n(x) { bit.assign(n + 1, 0); }

Here is the call graph for this function:

Member Function Documentation

offset()

int range_queries::fenwick_tree::offset ( int x )

inlineprivate

Returns the highest power of two which is not more than x.

Parameters

x	Index of element in original array.

Returns

Offset of index.

{ return (x & (-x)); }

sum()

template<typename T >

int range_queries::fenwick_tree::sum ( T id )

inline

Returns the sum of elements in range from 0 to ID.

Template Parameters

T	the type of the variables

Parameters

id	Index in original array up to which sum is evaluated.

Returns

Sum of elements in range from 0 to id.

                  {
        id++;
        T res = 0;
        while (id > 0) {
            res += bit[id];
            id -= offset(id);
        }
        return res;
    }

Here is the call graph for this function:

sum_range()

int range_queries::fenwick_tree::sum_range ( int l, int r )

inline

Returns the prefix sum in range from L to R.

Parameters

l	Left index of range.
r	Right index of range.

Returns

Sum of elements in range from L to R.

{ return sum(r) - sum(l - 1); }

Here is the call graph for this function:

update()

template<typename T >

void range_queries::fenwick_tree::update ( T id, T val )

inline

Updates the value of an element in original array and accordingly updates the values in BIT array.

Template Parameters

T	the type of the variables

Parameters

id	Index of element in original array.
val	Value with which element's value is updated.

Returns

void

                             {
        id++;
        while (id <= n) {
            bit[id] += val;
            id += offset(id);
        }
    }

Here is the call graph for this function:

Member Data Documentation

bit

std::vector<int> range_queries::fenwick_tree::bit {}

private

Array that represents Binary Indexed Tree.

{};  ///< Array that represents Binary Indexed Tree.

---

The documentation for this class was generated from the following file:

• range_queries/fenwick_tree.cpp