Struct BinaryIndexedTree 

pub struct BinaryIndexedTree<M>
where
    M: Monoid,
{
    n: usize,
    bit: Vec<M::T>,
}

Fields

n: usize

bit: Vec<M::T>

Implementations

impl<M> BinaryIndexedTree<M>

where M: Monoid,

pub fn new(n: usize) -> Self

Examples found in repository

crates/competitive/src/data_structure/range_frequency.rs (line 119)

    fn new(size: usize) -> Self {
        Self {
            bit: BinaryIndexedTree::new(size.div_ceil(64)),
            data: vec![0; size.div_ceil(64)],
        }
    }

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

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 {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                bit.update(p, x);
            }
            Query::Sum { l, r } => {
                writeln!(writer, "{}", bit.fold(l, r)).ok();
            }
        }
    }
}

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

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 = graph.path_euler_tour_builder(0).build();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);

    scan!(scanner, q);
    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { v, w } => {
                et.update(v, w, -w, |k, x| bit.update(k, x));
            }
            Query::Get { u } => {
                let ans = et.fold(u, |k| bit.accumulate(k));
                writeln!(writer, "{}", ans).ok();
            }
        }
    }
}

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

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 {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                bit.update(hld.vidx[p], x);
            }
            Query::Sum { u, v } => {
                writeln!(
                    writer,
                    "{}",
                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
                )
                .ok();
            }
        }
    }
}

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 21)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);

    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |start, end| {
                    bit.update(start, x);
                    bit.update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |i| ans += bit.accumulate(i));
                writeln!(writer, "{ans}").ok();
            }
        }
    }
}

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

Examples found in repository

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 25)

pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut raw = vec![0; cq.len()];
    for (v, &x) in a.iter().enumerate() {
        cq.for_each_index(v, |i| raw[i] += x);
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                cq.for_each_index(p, |i| bit.update(i, x));
            }
            Query::Sum { v, l, r } => {
                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
                cq.for_each_contour_range(v, l, r, |start, end| {
                    ans += bit.fold(start, end);
                });
                writeln!(writer, "{ans}").ok();
            }
        }
    }
}

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 73)

    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 37)

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 = graph.path_euler_tour_builder(0).build();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);

    scan!(scanner, q);
    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { v, w } => {
                et.update(v, w, -w, |k, x| bit.update(k, x));
            }
            Query::Get { u } => {
                let ans = et.fold(u, |k| bit.accumulate(k));
                writeln!(writer, "{}", ans).ok();
            }
        }
    }
}

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 37)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);

    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |start, end| {
                    bit.update(start, x);
                    bit.update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |i| ans += bit.accumulate(i));
                writeln!(writer, "{ans}").ok();
            }
        }
    }
}

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

Examples found in repository

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

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

crates/competitive/src/data_structure/range_frequency.rs (line 128)

    fn add(&mut self, index: usize) {
        let (block, bit) = (index / 64, index % 64);
        assert!(self.data[block] & (1 << bit) == 0);
        self.data[block] |= 1 << bit;
        self.bit.update(block, 1);
    }

    fn remove(&mut self, index: usize) {
        let (i, j) = (index / 64, index % 64);
        assert!(self.data[i] & (1 << j) != 0);
        self.data[i] &= !(1 << j);
        self.bit.update(i, -1);
    }

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

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 {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                bit.update(p, x);
            }
            Query::Sum { l, r } => {
                writeln!(writer, "{}", bit.fold(l, r)).ok();
            }
        }
    }
}

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 = graph.path_euler_tour_builder(0).build();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);

    scan!(scanner, q);
    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { v, w } => {
                et.update(v, w, -w, |k, x| bit.update(k, x));
            }
            Query::Get { u } => {
                let ans = et.fold(u, |k| bit.accumulate(k));
                writeln!(writer, "{}", ans).ok();
            }
        }
    }
}

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

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 {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                bit.update(hld.vidx[p], x);
            }
            Query::Sum { u, v } => {
                writeln!(
                    writer,
                    "{}",
                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
                )
                .ok();
            }
        }
    }
}

crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 28)

pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);

    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { v, l, r, x } => {
                cq.for_each_contour_range(v, l, r, |start, end| {
                    bit.update(start, x);
                    bit.update(end, -x);
                });
                if l == 0 && 0 < r {
                    a[v] += x;
                }
            }
            Query::Get { v } => {
                let mut ans = a[v];
                cq.for_each_index(v, |i| ans += bit.accumulate(i));
                writeln!(writer, "{ans}").ok();
            }
        }
    }
}

Additional examples can be found in:

• crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs

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 94)

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

crates/competitive/src/data_structure/range_frequency.rs (line 149)

    fn query(&self, left: usize, right: usize) -> usize {
        if left >= right {
            return 0;
        }
        let right = right - 1;
        let (li, lj) = (left / 64, left % 64);
        let (ri, rj) = (right / 64, right % 64);
        let rj_r = 63 - rj;
        if li == ri {
            (self.data[li] << rj_r >> (lj + rj_r)).count_ones() as usize
        } else {
            let mut ans = self.bit.fold(li + 1, ri) as usize;
            ans += (self.data[li] >> lj).count_ones() as usize;
            ans += (self.data[ri] << rj_r).count_ones() as usize;
            ans
        }
    }

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

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 {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                bit.update(p, x);
            }
            Query::Sum { l, r } => {
                writeln!(writer, "{}", bit.fold(l, r)).ok();
            }
        }
    }
}

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

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 {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                bit.update(hld.vidx[p], x);
            }
            Query::Sum { u, v } => {
                writeln!(
                    writer,
                    "{}",
                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
                )
                .ok();
            }
        }
    }
}

crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 36)

pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let cq = graph.contour_query_range();
    let mut raw = vec![0; cq.len()];
    for (v, &x) in a.iter().enumerate() {
        cq.for_each_index(v, |i| raw[i] += x);
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
    for _ in 0..q {
        scan!(scanner, query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                cq.for_each_index(p, |i| bit.update(i, x));
            }
            Query::Sum { v, l, r } => {
                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
                cq.for_each_contour_range(v, l, r, |start, end| {
                    ans += bit.fold(start, end);
                });
                writeln!(writer, "{ans}").ok();
            }
        }
    }
}

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

Examples found in repository

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

    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> BinaryIndexedTree<M>

where M: Monoid<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<T: Debug>,

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

Formats the value using the given formatter.