BinaryIndexedTree

competitive::data_structure

Struct BinaryIndexedTree 

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

Fields§

§n: usize§bit: Vec<M::T>

Implementations§

Source§

impl<M> BinaryIndexedTree<M>
where M: Monoid,

Source

pub fn new(n: usize) -> Self

Examples found in repository?
crates/competitive/src/data_structure/range_frequency.rs (line 119)
117    fn new(size: usize) -> Self {
118        Self {
119            bit: BinaryIndexedTree::new(size.div_ceil(64)),
120            data: vec![0; size.div_ceil(64)],
121        }
122    }
More examples
Hide additional examples
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 13)
9pub fn point_add_range_sum_binary_indexed_tree(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64]);
13    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
14    for (i, a) in a.take(n).enumerate() {
15        bit.update(i, a);
16    }
17    for _ in 0..q {
18        match scanner.scan::<usize>() {
19            0 => {
20                scan!(scanner, p, x: i64);
21                bit.update(p, x);
22            }
23            1 => {
24                scan!(scanner, l, r);
25                writeln!(writer, "{}", bit.fold(l, r)).ok();
26            }
27            _ => unreachable!("unknown query"),
28        }
29    }
30}
crates/library_checker/src/tree/vertex_add_path_sum.rs (line 14)
9pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
13    let hld = HeavyLightDecomposition::new(0, &mut graph);
14    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
15    for (i, a) in a.iter().cloned().enumerate() {
16        bit.update(hld.vidx[i], a);
17    }
18    for _ in 0..q {
19        match scanner.scan::<usize>() {
20            0 => {
21                scan!(scanner, p, x: i64);
22                bit.update(hld.vidx[p], x);
23            }
24            1 => {
25                scan!(scanner, u, v);
26                writeln!(
27                    writer,
28                    "{}",
29                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
30                )
31                .ok();
32            }
33            _ => unreachable!("unknown query"),
34        }
35    }
36}
crates/aizu_online_judge/src/grl/grl_5_d.rs (line 20)
9pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, c: [SizedCollect<usize>]);
13    let edges = c
14        .take(n)
15        .enumerate()
16        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
17        .collect();
18    let graph = UndirectedSparseGraph::from_edges(n, edges);
19    let et = EulerTourForEdge::new(0, &graph);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());
21
22    scan!(scanner, q);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, v, w: i64);
27                let (l, r) = et.eidx[et.par[v]];
28                bit.update(l, w);
29                bit.update(r, -w);
30            }
31            1 => {
32                scan!(scanner, u);
33                let ans = if u > 0 {
34                    bit.accumulate(et.eidx[et.par[u]].0)
35                } else {
36                    0
37                };
38                writeln!(writer, "{}", ans).ok();
39            }
40            _ => unreachable!("unknown query"),
41        }
42    }
43}
Source

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

Source

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)
72    pub fn accumulate(&self, k: usize) -> M::T {
73        self.accumulate0(k + 1)
74    }
75    #[inline]
76    pub fn update(&mut self, k: usize, x: M::T) {
77        debug_assert!(k < self.n);
78        let mut k = k + 1;
79        while k <= self.n {
80            self.bit[k] = M::operate(&self.bit[k], &x);
81            k += k & (!k + 1);
82        }
83    }
84}
85
86impl<G: Group> BinaryIndexedTree<G> {
87    #[inline]
88    pub fn fold(&self, l: usize, r: usize) -> G::T {
89        debug_assert!(l <= self.n && r <= self.n);
90        G::operate(&G::inverse(&self.accumulate0(l)), &self.accumulate0(r))
91    }
Source

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)
9pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, c: [SizedCollect<usize>]);
13    let edges = c
14        .take(n)
15        .enumerate()
16        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
17        .collect();
18    let graph = UndirectedSparseGraph::from_edges(n, edges);
19    let et = EulerTourForEdge::new(0, &graph);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());
21
22    scan!(scanner, q);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, v, w: i64);
27                let (l, r) = et.eidx[et.par[v]];
28                bit.update(l, w);
29                bit.update(r, -w);
30            }
31            1 => {
32                scan!(scanner, u);
33                let ans = if u > 0 {
34                    bit.accumulate(et.eidx[et.par[u]].0)
35                } else {
36                    0
37                };
38                writeln!(writer, "{}", ans).ok();
39            }
40            _ => unreachable!("unknown query"),
41        }
42    }
43}
Source

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)
97    pub fn set(&mut self, k: usize, x: G::T) {
98        self.update(k, G::operate(&G::inverse(&self.get(k)), &x));
99    }
More examples
Hide additional examples
crates/competitive/src/data_structure/range_frequency.rs (line 128)
124    fn add(&mut self, index: usize) {
125        let (block, bit) = (index / 64, index % 64);
126        assert!(self.data[block] & (1 << bit) == 0);
127        self.data[block] |= 1 << bit;
128        self.bit.update(block, 1);
129    }
130
131    fn remove(&mut self, index: usize) {
132        let (i, j) = (index / 64, index % 64);
133        assert!(self.data[i] & (1 << j) != 0);
134        self.data[i] &= !(1 << j);
135        self.bit.update(i, -1);
136    }
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 15)
9pub fn point_add_range_sum_binary_indexed_tree(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64]);
13    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
14    for (i, a) in a.take(n).enumerate() {
15        bit.update(i, a);
16    }
17    for _ in 0..q {
18        match scanner.scan::<usize>() {
19            0 => {
20                scan!(scanner, p, x: i64);
21                bit.update(p, x);
22            }
23            1 => {
24                scan!(scanner, l, r);
25                writeln!(writer, "{}", bit.fold(l, r)).ok();
26            }
27            _ => unreachable!("unknown query"),
28        }
29    }
30}
crates/library_checker/src/tree/vertex_add_path_sum.rs (line 16)
9pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
13    let hld = HeavyLightDecomposition::new(0, &mut graph);
14    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
15    for (i, a) in a.iter().cloned().enumerate() {
16        bit.update(hld.vidx[i], a);
17    }
18    for _ in 0..q {
19        match scanner.scan::<usize>() {
20            0 => {
21                scan!(scanner, p, x: i64);
22                bit.update(hld.vidx[p], x);
23            }
24            1 => {
25                scan!(scanner, u, v);
26                writeln!(
27                    writer,
28                    "{}",
29                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
30                )
31                .ok();
32            }
33            _ => unreachable!("unknown query"),
34        }
35    }
36}
crates/aizu_online_judge/src/grl/grl_5_d.rs (line 28)
9pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, c: [SizedCollect<usize>]);
13    let edges = c
14        .take(n)
15        .enumerate()
16        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
17        .collect();
18    let graph = UndirectedSparseGraph::from_edges(n, edges);
19    let et = EulerTourForEdge::new(0, &graph);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());
21
22    scan!(scanner, q);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, v, w: i64);
27                let (l, r) = et.eidx[et.par[v]];
28                bit.update(l, w);
29                bit.update(r, -w);
30            }
31            1 => {
32                scan!(scanner, u);
33                let ans = if u > 0 {
34                    bit.accumulate(et.eidx[et.par[u]].0)
35                } else {
36                    0
37                };
38                writeln!(writer, "{}", ans).ok();
39            }
40            _ => unreachable!("unknown query"),
41        }
42    }
43}
Source§

impl<G: Group> BinaryIndexedTree<G>

Source

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)
93    pub fn get(&self, k: usize) -> G::T {
94        self.fold(k, k + 1)
95    }
More examples
Hide additional examples
crates/competitive/src/data_structure/range_frequency.rs (line 149)
138    fn query(&self, left: usize, right: usize) -> usize {
139        if left >= right {
140            return 0;
141        }
142        let right = right - 1;
143        let (li, lj) = (left / 64, left % 64);
144        let (ri, rj) = (right / 64, right % 64);
145        let rj_r = 63 - rj;
146        if li == ri {
147            (self.data[li] << rj_r >> (lj + rj_r)).count_ones() as usize
148        } else {
149            let mut ans = self.bit.fold(li + 1, ri) as usize;
150            ans += (self.data[li] >> lj).count_ones() as usize;
151            ans += (self.data[ri] << rj_r).count_ones() as usize;
152            ans
153        }
154    }
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 25)
9pub fn point_add_range_sum_binary_indexed_tree(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64]);
13    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
14    for (i, a) in a.take(n).enumerate() {
15        bit.update(i, a);
16    }
17    for _ in 0..q {
18        match scanner.scan::<usize>() {
19            0 => {
20                scan!(scanner, p, x: i64);
21                bit.update(p, x);
22            }
23            1 => {
24                scan!(scanner, l, r);
25                writeln!(writer, "{}", bit.fold(l, r)).ok();
26            }
27            _ => unreachable!("unknown query"),
28        }
29    }
30}
crates/library_checker/src/tree/vertex_add_path_sum.rs (line 29)
9pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
13    let hld = HeavyLightDecomposition::new(0, &mut graph);
14    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
15    for (i, a) in a.iter().cloned().enumerate() {
16        bit.update(hld.vidx[i], a);
17    }
18    for _ in 0..q {
19        match scanner.scan::<usize>() {
20            0 => {
21                scan!(scanner, p, x: i64);
22                bit.update(hld.vidx[p], x);
23            }
24            1 => {
25                scan!(scanner, u, v);
26                writeln!(
27                    writer,
28                    "{}",
29                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
30                )
31                .ok();
32            }
33            _ => unreachable!("unknown query"),
34        }
35    }
36}
Source

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

Examples found in repository?
crates/competitive/src/data_structure/binary_indexed_tree.rs (line 98)
97    pub fn set(&mut self, k: usize, x: G::T) {
98        self.update(k, G::operate(&G::inverse(&self.get(k)), &x));
99    }
Source

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

Source§

impl<M> BinaryIndexedTree<M>
where M: Monoid<T: Ord>,

Source

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

Trait Implementations§

Source§

impl<M> Clone for BinaryIndexedTree<M>
where M: Monoid,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<M> Debug for BinaryIndexedTree<M>
where M: Monoid<T: Debug>,

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<M> Freeze for BinaryIndexedTree<M>

§

impl<M> RefUnwindSafe for BinaryIndexedTree<M>
where <M as Magma>::T: RefUnwindSafe,

§

impl<M> Send for BinaryIndexedTree<M>
where <M as Magma>::T: Send,

§

impl<M> Sync for BinaryIndexedTree<M>
where <M as Magma>::T: Sync,

§

impl<M> Unpin for BinaryIndexedTree<M>
where <M as Magma>::T: Unpin,

§

impl<M> UnwindSafe for BinaryIndexedTree<M>
where <M as Magma>::T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.