operations_research::BinaryIndexedTree< T > Class Template Reference

#include <binary_indexed_tree.h>

Public Member Functions
	BinaryIndexedTree (int n)
void	AddItem (int index, T value)
	Adds value to index-th number.
T	GetPrefixSum (int index) const
int	size () const
	Returns the size of the tree.

Detailed Description

template<typename T>
class operations_research::BinaryIndexedTree< T >

A binary indexed tree is a data structure that represents an array of numbers and supports two operations: 1) add a number to i-th element of the array. 2) find the sum of a prefix of the array (elements from 0-th to j-th). See http://en.wikipedia.org/wiki/Fenwick_tree.

Definition at line 29 of file binary_indexed_tree.h.

Constructor & Destructor Documentation

BinaryIndexedTree()

template<typename T >

operations_research::BinaryIndexedTree< T >::BinaryIndexedTree ( int n )

inlineexplicit

Initializes the storage for a binary indexed tree of a given size. The tree contains all zeros initially.

Definition at line 33 of file binary_indexed_tree.h.

Member Function Documentation

AddItem()

template<typename T >

void operations_research::BinaryIndexedTree< T >::AddItem ( int index, T value )

inline

Adds value to index-th number.

Internal indices of BinaryIndexedTree are 1 based.

Definition at line 36 of file binary_indexed_tree.h.

GetPrefixSum()

template<typename T >

T operations_research::BinaryIndexedTree< T >::GetPrefixSum ( int index ) const

inline

Finds the sum of a prefix [0, index]. Passing index == -1 is allowed, will return 0 in that case.

Internal indices of BinaryIndexedTree are 1 based.

Definition at line 49 of file binary_indexed_tree.h.

size()

template<typename T >

int operations_research::BinaryIndexedTree< T >::size ( ) const

inline

Returns the size of the tree.

Definition at line 63 of file binary_indexed_tree.h.

---

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

• ortools/algorithms/binary_indexed_tree.h