The class that initializes the Fenwick Tree.
More...
|
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.
|
|
|
int | offset (int x) |
| Returns the highest power of two which is not more than x .
|
|
|
size_t | n = 0 |
| No. of elements present in input array.
|
|
std::vector< int > | bit {} |
| Array that represents Binary Indexed Tree.
|
|
The class that initializes the Fenwick Tree.
◆ fenwick_tree() [1/2]
template<typename T >
range_queries::fenwick_tree::fenwick_tree |
( |
const std::vector< T > & | arr | ) |
|
|
inlineexplicit |
Class Constructor.
- Template Parameters
-
- Parameters
-
[in] | arr | Input array for which prefix sum is evaluated. |
- Returns
- void
52 for (
int i = 0; i <
n; ++i) {
54 }
55 }
void update(T id, T val)
Updates the value of an element in original array and accordingly updates the values in BIT array.
Definition fenwick_tree.cpp:75
std::vector< int > bit
Array that represents Binary Indexed Tree.
Definition fenwick_tree.cpp:34
size_t n
No. of elements present in input array.
Definition fenwick_tree.cpp:33
◆ 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
◆ 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.
◆ 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.
90 {
91 id++;
92 T res = 0;
93 while (id > 0) {
96 }
97 return res;
98 }
int offset(int x)
Returns the highest power of two which is not more than x.
Definition fenwick_tree.cpp:41
◆ 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.
106{
return sum(r) -
sum(l - 1); }
int sum(T id)
Returns the sum of elements in range from 0 to ID.
Definition fenwick_tree.cpp:90
◆ 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
◆ bit
Array that represents Binary Indexed Tree.
The documentation for this class was generated from the following file: