Struct SegmentTree 

pub struct SegmentTree { /* private fields */ }

A segment tree supporting range sum queries and point updates.

Both query and update run in O(log n) time.

Implementations

impl SegmentTree

pub fn new(values: &[i64]) -> Self

Build a segment tree from a slice of values.

Time complexity: O(n).

pub fn query(&self, l: usize, r: usize) -> i64

Query the sum over the index range [l, r] (inclusive).

Returns 0 for an empty range or out-of-bounds query. Time complexity: O(log n).

pub fn update(&mut self, idx: usize, value: i64)

Update the element at index idx to value.

Time complexity: O(log n).

pub fn len(&self) -> usize

Return the number of leaf elements in the tree.

pub fn is_empty(&self) -> bool

Return true if the tree has no elements.