FenwickTree Class Reference

Collaboration diagram for FenwickTree:

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.

                                                    {
        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:

FenwickTree() [2/2]

FenwickTree::FenwickTree ( int  x )

inlineexplicit

Constructor

Parameters

[in]

x

--> Size of array that represents Binary Indexed Tree.

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

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

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

sum()

int FenwickTree::sum ( int  id )

inline

Get prefix sum upto id

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

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

{ 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

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

Here is the call graph for this function:

---

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

• range_queries/fenwick_tree.cpp