Struct BinaryIndexedTree 

pub struct BinaryIndexedTree<M>
where
    M: Monoid,
{ /* private fields */ }

Implementations

impl<M> BinaryIndexedTree<M>

where M: Monoid,

pub fn new(n: usize) -> Self

Examples found in repository

crates/library_checker/src/data_structure/point_add_range_sum.rs (line 13)

pub fn point_add_range_sum_binary_indexed_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [i64]);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
    for (i, a) in a.take(n).enumerate() {
        bit.update(i, a);
    }
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, p, x: i64);
                bit.update(p, x);
            }
            1 => {
                scan!(scanner, l, r);
                writeln!(writer, "{}", bit.fold(l, r)).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 14)

pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = HeavyLightDecomposition::new(0, &mut graph);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
    for (i, a) in a.iter().cloned().enumerate() {
        bit.update(hld.vidx[i], a);
    }
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, p, x: i64);
                bit.update(hld.vidx[p], x);
            }
            1 => {
                scan!(scanner, u, v);
                writeln!(
                    writer,
                    "{}",
                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
                )
                .ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 20)

pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, c: [SizedCollect<usize>]);
    let edges = c
        .take(n)
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = EulerTourForEdge::new(0, &graph);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());

    scan!(scanner, q);
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, v, w: i64);
                let (l, r) = et.eidx[et.par[v]];
                bit.update(l, w);
                bit.update(r, -w);
            }
            1 => {
                scan!(scanner, u);
                let ans = if u > 0 {
                    bit.accumulate(et.eidx[et.par[u]].0)
                } else {
                    0
                };
                writeln!(writer, "{}", ans).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

pub fn from_slice(slice: &[M::T]) -> Self

pub fn accumulate0(&self, k: usize) -> M::T

fold [0, k)

Examples found in repository

crates/competitive/src/data_structure/binary_indexed_tree.rs (line 74)

    pub fn accumulate(&self, k: usize) -> M::T {
        self.accumulate0(k + 1)
    }
    #[inline]
    pub fn update(&mut self, k: usize, x: M::T) {
        debug_assert!(k < self.n);
        let mut k = k + 1;
        while k <= self.n {
            self.bit[k] = M::operate(&self.bit[k], &x);
            k += k & (!k + 1);
        }
    }
}

impl<G: Group> BinaryIndexedTree<G> {
    #[inline]
    pub fn fold(&self, l: usize, r: usize) -> G::T {
        debug_assert!(l <= self.n && r <= self.n);
        G::operate(&G::inverse(&self.accumulate0(l)), &self.accumulate0(r))
    }

pub fn accumulate(&self, k: usize) -> M::T

fold [0, k]

Examples found in repository

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 34)

pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, c: [SizedCollect<usize>]);
    let edges = c
        .take(n)
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = EulerTourForEdge::new(0, &graph);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());

    scan!(scanner, q);
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, v, w: i64);
                let (l, r) = et.eidx[et.par[v]];
                bit.update(l, w);
                bit.update(r, -w);
            }
            1 => {
                scan!(scanner, u);
                let ans = if u > 0 {
                    bit.accumulate(et.eidx[et.par[u]].0)
                } else {
                    0
                };
                writeln!(writer, "{}", ans).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

pub fn update(&mut self, k: usize, x: M::T)

Examples found in repository

crates/competitive/src/data_structure/binary_indexed_tree.rs (line 99)

    pub fn set(&mut self, k: usize, x: G::T) {
        self.update(k, G::operate(&G::inverse(&self.get(k)), &x));
    }

crates/library_checker/src/data_structure/point_add_range_sum.rs (line 15)

pub fn point_add_range_sum_binary_indexed_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [i64]);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
    for (i, a) in a.take(n).enumerate() {
        bit.update(i, a);
    }
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, p, x: i64);
                bit.update(p, x);
            }
            1 => {
                scan!(scanner, l, r);
                writeln!(writer, "{}", bit.fold(l, r)).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 16)

pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = HeavyLightDecomposition::new(0, &mut graph);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
    for (i, a) in a.iter().cloned().enumerate() {
        bit.update(hld.vidx[i], a);
    }
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, p, x: i64);
                bit.update(hld.vidx[p], x);
            }
            1 => {
                scan!(scanner, u, v);
                writeln!(
                    writer,
                    "{}",
                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
                )
                .ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 28)

pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, c: [SizedCollect<usize>]);
    let edges = c
        .take(n)
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = EulerTourForEdge::new(0, &graph);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());

    scan!(scanner, q);
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, v, w: i64);
                let (l, r) = et.eidx[et.par[v]];
                bit.update(l, w);
                bit.update(r, -w);
            }
            1 => {
                scan!(scanner, u);
                let ans = if u > 0 {
                    bit.accumulate(et.eidx[et.par[u]].0)
                } else {
                    0
                };
                writeln!(writer, "{}", ans).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

impl<G: Group> BinaryIndexedTree<G>

pub fn fold(&self, l: usize, r: usize) -> G::T

Examples found in repository

crates/competitive/src/data_structure/binary_indexed_tree.rs (line 95)

    pub fn get(&self, k: usize) -> G::T {
        self.fold(k, k + 1)
    }

crates/library_checker/src/data_structure/point_add_range_sum.rs (line 25)

pub fn point_add_range_sum_binary_indexed_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [i64]);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
    for (i, a) in a.take(n).enumerate() {
        bit.update(i, a);
    }
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, p, x: i64);
                bit.update(p, x);
            }
            1 => {
                scan!(scanner, l, r);
                writeln!(writer, "{}", bit.fold(l, r)).ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 29)

pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = HeavyLightDecomposition::new(0, &mut graph);
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
    for (i, a) in a.iter().cloned().enumerate() {
        bit.update(hld.vidx[i], a);
    }
    for _ in 0..q {
        match scanner.scan::<usize>() {
            0 => {
                scan!(scanner, p, x: i64);
                bit.update(hld.vidx[p], x);
            }
            1 => {
                scan!(scanner, u, v);
                writeln!(
                    writer,
                    "{}",
                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
                )
                .ok();
            }
            _ => panic!("unknown query"),
        }
    }
}

pub fn get(&self, k: usize) -> G::T

Examples found in repository

crates/competitive/src/data_structure/binary_indexed_tree.rs (line 99)

    pub fn set(&mut self, k: usize, x: G::T) {
        self.update(k, G::operate(&G::inverse(&self.get(k)), &x));
    }

pub fn set(&mut self, k: usize, x: G::T)

impl<M: Monoid> BinaryIndexedTree<M>

where M::T: Ord,

pub fn lower_bound(&self, x: M::T) -> usize

Trait Implementations

impl<M> Clone for BinaryIndexedTree<M>

where M: Monoid,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<M> Debug for BinaryIndexedTree<M>

where M: Monoid, M::T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.