Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
FenwickTree Class Reference
Collaboration diagram for FenwickTree:
[legend]

Public Member Functions

 FenwickTree (const std::vector< int > &arr)
 
 FenwickTree (int x)
 
void update (int id, int val)
 
int sum (int id)
 
int sum_range (int l, int r)
 

Private Member Functions

int offset (int x)
 

Private Attributes

int n
 
std::vector< int > bit
 

Detailed Description

n --> No. of elements present in input array. bit[0..n] --> Array that represents Binary Indexed Tree.

Constructor & Destructor Documentation

◆ FenwickTree() [1/2]

FenwickTree::FenwickTree ( const std::vector< int > &  arr)
inlineexplicit

Constructor

Parameters
[in]arr--> Input array for which prefix sum is evaluated.
28  {
29  n = arr.size();
30  bit.assign(n + 1, 0);
31  for (int i = 0; i < n; ++i) {
32  update(i, arr[i]);
33  }
34  }
Here is the call graph for this function:

◆ FenwickTree() [2/2]

FenwickTree::FenwickTree ( int  x)
inlineexplicit

Constructor

Parameters
[in]x--> Size of array that represents Binary Indexed Tree.
39  {
40  n = x;
41  bit.assign(n + 1, 0);
42  }
Here is the call graph for this function:

Member Function Documentation

◆ offset()

int FenwickTree::offset ( int  x)
inlineprivate

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

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

◆ sum()

int FenwickTree::sum ( int  id)
inline

Get prefix sum upto id

54  {
55  id++;
56  int res = 0;
57  while (id > 0) {
58  res += bit[id];
59  id -= offset(id);
60  }
61  return res;
62  }
Here is the call graph for this function:

◆ sum_range()

int FenwickTree::sum_range ( int  l,
int  r 
)
inline

Returns the prefix sum in range from l to r

65 { return sum(r) - sum(l - 1); }
Here is the call graph for this function:

◆ update()

void FenwickTree::update ( int  id,
int  val 
)
inline

Add val at id

45  {
46  id++;
47  while (id <= n) {
48  bit[id] += val;
49  id += offset(id);
50  }
51  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
std::vector::size
T size(T... args)
FenwickTree::offset
int offset(int x)
Definition: fenwick_tree.cpp:22
FenwickTree::update
void update(int id, int val)
Definition: fenwick_tree.cpp:45
std::vector::assign
T assign(T... args)
FenwickTree::sum
int sum(int id)
Definition: fenwick_tree.cpp:54