Struct BIT

pub struct BIT { /* private fields */ }

Binary Indexed Tree (0-indexed)

This data structure supports these two queries in O(log n)

1. add w to v[at]
2. the sum of v[begin], v[begin+1], .., v[end-1]

Implementations

impl BIT

pub fn new(len: usize) -> BIT

Constructs a new BIT of length len. All values are initialized zero.

Examples

use algonium::data_structure::BIT;
let mut bit = BIT::new(100);

pub fn len(&self) -> usize

Returns the number of elements in the BIT.

Examples

use algonium::data_structure::BIT;
let mut bit = BIT::new(100);
assert_eq!(bit.len(), 100);

pub fn add(&mut self, index: usize, value: i64)

Add a value value to a element of index index. v[index] += value

Panics

Panics if index > len

Examples

use algonium::data_structure::BIT;
let mut bit = BIT::new(10);
bit.add(5, 100);
assert_eq!(bit.get(3, 6), 100);
bit.add(5, 10);
assert_eq!(bit.get(3, 6), 110);

pub fn get(&self, begin: usize, end: usize) -> i64

sum of v[idx] such that begin <= idx < end