Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
fenwick_tree.cpp File Reference

Fenwick tree. More...

#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for fenwick_tree.cpp:

Classes

class  FenwickTree
 

Functions

int main ()
 

Detailed Description

Fenwick tree.

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Function Documentation

◆ main()

int main ( void  )

Main function

69  {
70  int n = 5;
71  std::vector<int> arr = {1, 2, 3, 4, 5};
72  FenwickTree fenwick_tree(arr);
73 
74  assert(fenwick_tree.sum_range(0, 0) == 1);
75  assert(fenwick_tree.sum_range(0, 1) == 3);
76  assert(fenwick_tree.sum_range(0, 2) == 6);
77  fenwick_tree.update(0, 6);
78  assert(fenwick_tree.sum_range(0, 0) == 6);
79  assert(fenwick_tree.sum_range(0, 1) == 8);
80  assert(fenwick_tree.sum_range(0, 2) == 11);
81  return 0;
82 }
Here is the call graph for this function:
std::vector< int >
FenwickTree
Definition: fenwick_tree.cpp:17