Struct PrefixSum 

pub struct PrefixSum { /* private fields */ }

Prefix-sum array over a slice of integers.

Supports O(1) range-sum queries after O(n) construction.

Example

let ps = PrefixSum::build(&[1, 2, 3, 4, 5]);
assert_eq!(ps.range_sum(1, 3), 9); // 2 + 3 + 4

Implementations

impl PrefixSum

pub fn build(data: &[i64]) -> Self

Build a prefix-sum structure from a slice.

prefix[0] = 0, prefix[i+1] = prefix[i] + data[i].

pub fn range_sum(&self, lo: usize, hi: usize) -> i64

Query the inclusive range sum data[lo..=hi].

Returns the sum of elements from index lo to hi inclusive. Panics if lo > hi or indices are out of range.

pub fn len(&self) -> usize

Number of original data elements.

pub fn is_empty(&self) -> bool

Returns true if there are no data elements.