Skip to main content

DaryPrefixSumTreeU32

competitive::data_structure

Struct DaryPrefixSumTreeU32 

Source 
pub struct DaryPrefixSumTreeU32 {
    levels: Vec<Vec<PrefixBlock<u32, 16>>>,
    len: usize,
    total: u32,
    partition_valid: bool,
    backend: SimdBackend,
}
Expand description

A cache-line-oriented d-ary tree for point updates, prefix sums, and prefix searches.

BinaryIndexedTree has a denser layout and can be preferable for small workloads. Use this type for repeated updates and prefix searches, especially with SIMD support.

Fields§

§levels: Vec<Vec<PrefixBlock<u32, 16>>>§len: usize§total: u32§partition_valid: bool§backend: SimdBackend

Implementations§

Source§

impl DaryPrefixSumTreeU32

Source

pub fn new(len: usize) -> Self

Examples found in repository?
crates/library_checker/src/data_structure/static_range_count_distinct.rs (line 25)
5pub fn static_range_count_distinct(reader: impl Read, writer: impl Write) {
6    prepare_io!(buffered; reader, writer);
7    sc!(n, q, a: [u32; n], queries: [(usize, usize); q]);
8    let end = queries.iter().map(|&(_, r)| r).max().unwrap_or(0);
9    if end == 0 {
10        pp!(@lf @it std::iter::repeat_n(0u32, q));
11        return;
12    }
13    let mut offsets = vec![0; end + 2];
14    for &(_, r) in &queries {
15        offsets[r] += 1;
16    }
17    for r in 0..=end {
18        offsets[r + 1] += offsets[r];
19    }
20    let mut order = vec![(0, 0); q];
21    for (i, (l, r)) in queries.into_iter().enumerate() {
22        offsets[r] -= 1;
23        order[offsets[r]] = (l as u32, i as u32);
24    }
25    let mut bit = DaryPrefixSumTreeU32::new(end + 1);
26    let mut last = FibHashMap::default();
27    let mut ans = vec![0; q];
28    for r in 0..=end {
29        if r != 0 {
30            let previous = last.insert(a[r - 1], r).unwrap_or(0);
31            bit.update(previous, 1);
32        }
33        for &(l, i) in &order[offsets[r]..offsets[r + 1]] {
34            ans[i as usize] = bit.accumulate0(l as usize + 1) - l;
35        }
36    }
37    pp!(@lf @it ans);
38}
Source

pub fn from_slice(values: &[u32]) -> Self

Examples found in repository?
crates/library_checker/src/data_structure/ordered_set.rs (line 33)
8pub fn ordered_set(reader: impl Read, writer: impl Write) {
9    prepare_io!(buffered; reader, writer);
10    sc!(n, q, a: [u32; n], queries: [(u8, u32); q]);
11    let mut values: Vec<_> = a
12        .iter()
13        .copied()
14        .chain(queries.iter().filter_map(|&(t, x)| (t <= 1).then_some(x)))
15        .collect();
16    values.radix_sort_by_key(|&x| x);
17    values.dedup();
18    let search = StaticSearch::from_sorted(&values);
19    let endpoints: Vec<_> = a
20        .into_iter()
21        .chain(
22            queries
23                .iter()
24                .map(|&(t, x)| if t == 3 || t == 4 { x + 1 } else { x }),
25        )
26        .collect();
27    let mut positions = vec![0; endpoints.len()];
28    search.lower_bound_batch(&endpoints, &mut positions);
29    let mut counts = vec![0; values.len()];
30    for &k in &positions[..n] {
31        counts[k] = 1;
32    }
33    let mut seg = DaryPrefixSumTreeU32::from_slice(&counts);
34    for ((t, x), &k) in queries.into_iter().zip(&positions[n..]) {
35        match t {
36            0 => seg.set(k, 1),
37            1 => seg.set(k, 0),
38            2 => {
39                let k = seg.partition_point_acc(x - 1);
40                pp!(values.get(k).map_or(-1, |&x| x as i64));
41            }
42            3 => {
43                pp!(seg.accumulate0(k));
44            }
45            4 => {
46                let count = seg.accumulate0(k);
47                pp!(if count == 0 {
48                    -1
49                } else {
50                    values[seg.partition_point_acc(count - 1)] as i64
51                });
52            }
53            5 => {
54                let count = seg.accumulate0(k);
55                let k = seg.partition_point_acc(count);
56                pp!(values.get(k).map_or(-1, |&x| x as i64));
57            }
58            _ => unreachable!(),
59        }
60    }
61}
Source

pub fn len(&self) -> usize

Source

pub fn is_empty(&self) -> bool

Source

pub fn update(&mut self, index: usize, value: u32)

Adds value at index. Arithmetic is wrapping.

Examples found in repository?
crates/library_checker/src/data_structure/static_range_count_distinct.rs (line 31)
5pub fn static_range_count_distinct(reader: impl Read, writer: impl Write) {
6    prepare_io!(buffered; reader, writer);
7    sc!(n, q, a: [u32; n], queries: [(usize, usize); q]);
8    let end = queries.iter().map(|&(_, r)| r).max().unwrap_or(0);
9    if end == 0 {
10        pp!(@lf @it std::iter::repeat_n(0u32, q));
11        return;
12    }
13    let mut offsets = vec![0; end + 2];
14    for &(_, r) in &queries {
15        offsets[r] += 1;
16    }
17    for r in 0..=end {
18        offsets[r + 1] += offsets[r];
19    }
20    let mut order = vec![(0, 0); q];
21    for (i, (l, r)) in queries.into_iter().enumerate() {
22        offsets[r] -= 1;
23        order[offsets[r]] = (l as u32, i as u32);
24    }
25    let mut bit = DaryPrefixSumTreeU32::new(end + 1);
26    let mut last = FibHashMap::default();
27    let mut ans = vec![0; q];
28    for r in 0..=end {
29        if r != 0 {
30            let previous = last.insert(a[r - 1], r).unwrap_or(0);
31            bit.update(previous, 1);
32        }
33        for &(l, i) in &order[offsets[r]..offsets[r + 1]] {
34            ans[i as usize] = bit.accumulate0(l as usize + 1) - l;
35        }
36    }
37    pp!(@lf @it ans);
38}
Source

pub fn set(&mut self, index: usize, value: u32)

Replaces the value at index. Arithmetic is wrapping.

Examples found in repository?
crates/library_checker/src/data_structure/ordered_set.rs (line 36)
8pub fn ordered_set(reader: impl Read, writer: impl Write) {
9    prepare_io!(buffered; reader, writer);
10    sc!(n, q, a: [u32; n], queries: [(u8, u32); q]);
11    let mut values: Vec<_> = a
12        .iter()
13        .copied()
14        .chain(queries.iter().filter_map(|&(t, x)| (t <= 1).then_some(x)))
15        .collect();
16    values.radix_sort_by_key(|&x| x);
17    values.dedup();
18    let search = StaticSearch::from_sorted(&values);
19    let endpoints: Vec<_> = a
20        .into_iter()
21        .chain(
22            queries
23                .iter()
24                .map(|&(t, x)| if t == 3 || t == 4 { x + 1 } else { x }),
25        )
26        .collect();
27    let mut positions = vec![0; endpoints.len()];
28    search.lower_bound_batch(&endpoints, &mut positions);
29    let mut counts = vec![0; values.len()];
30    for &k in &positions[..n] {
31        counts[k] = 1;
32    }
33    let mut seg = DaryPrefixSumTreeU32::from_slice(&counts);
34    for ((t, x), &k) in queries.into_iter().zip(&positions[n..]) {
35        match t {
36            0 => seg.set(k, 1),
37            1 => seg.set(k, 0),
38            2 => {
39                let k = seg.partition_point_acc(x - 1);
40                pp!(values.get(k).map_or(-1, |&x| x as i64));
41            }
42            3 => {
43                pp!(seg.accumulate0(k));
44            }
45            4 => {
46                let count = seg.accumulate0(k);
47                pp!(if count == 0 {
48                    -1
49                } else {
50                    values[seg.partition_point_acc(count - 1)] as i64
51                });
52            }
53            5 => {
54                let count = seg.accumulate0(k);
55                let k = seg.partition_point_acc(count);
56                pp!(values.get(k).map_or(-1, |&x| x as i64));
57            }
58            _ => unreachable!(),
59        }
60    }
61}
Source

pub fn accumulate0(&self, end: usize) -> u32

Returns the wrapping sum of 0..end.

Examples found in repository?
crates/library_checker/src/data_structure/static_range_count_distinct.rs (line 34)
5pub fn static_range_count_distinct(reader: impl Read, writer: impl Write) {
6    prepare_io!(buffered; reader, writer);
7    sc!(n, q, a: [u32; n], queries: [(usize, usize); q]);
8    let end = queries.iter().map(|&(_, r)| r).max().unwrap_or(0);
9    if end == 0 {
10        pp!(@lf @it std::iter::repeat_n(0u32, q));
11        return;
12    }
13    let mut offsets = vec![0; end + 2];
14    for &(_, r) in &queries {
15        offsets[r] += 1;
16    }
17    for r in 0..=end {
18        offsets[r + 1] += offsets[r];
19    }
20    let mut order = vec![(0, 0); q];
21    for (i, (l, r)) in queries.into_iter().enumerate() {
22        offsets[r] -= 1;
23        order[offsets[r]] = (l as u32, i as u32);
24    }
25    let mut bit = DaryPrefixSumTreeU32::new(end + 1);
26    let mut last = FibHashMap::default();
27    let mut ans = vec![0; q];
28    for r in 0..=end {
29        if r != 0 {
30            let previous = last.insert(a[r - 1], r).unwrap_or(0);
31            bit.update(previous, 1);
32        }
33        for &(l, i) in &order[offsets[r]..offsets[r + 1]] {
34            ans[i as usize] = bit.accumulate0(l as usize + 1) - l;
35        }
36    }
37    pp!(@lf @it ans);
38}
More examples
Hide additional examples
crates/library_checker/src/data_structure/ordered_set.rs (line 43)
8pub fn ordered_set(reader: impl Read, writer: impl Write) {
9    prepare_io!(buffered; reader, writer);
10    sc!(n, q, a: [u32; n], queries: [(u8, u32); q]);
11    let mut values: Vec<_> = a
12        .iter()
13        .copied()
14        .chain(queries.iter().filter_map(|&(t, x)| (t <= 1).then_some(x)))
15        .collect();
16    values.radix_sort_by_key(|&x| x);
17    values.dedup();
18    let search = StaticSearch::from_sorted(&values);
19    let endpoints: Vec<_> = a
20        .into_iter()
21        .chain(
22            queries
23                .iter()
24                .map(|&(t, x)| if t == 3 || t == 4 { x + 1 } else { x }),
25        )
26        .collect();
27    let mut positions = vec![0; endpoints.len()];
28    search.lower_bound_batch(&endpoints, &mut positions);
29    let mut counts = vec![0; values.len()];
30    for &k in &positions[..n] {
31        counts[k] = 1;
32    }
33    let mut seg = DaryPrefixSumTreeU32::from_slice(&counts);
34    for ((t, x), &k) in queries.into_iter().zip(&positions[n..]) {
35        match t {
36            0 => seg.set(k, 1),
37            1 => seg.set(k, 0),
38            2 => {
39                let k = seg.partition_point_acc(x - 1);
40                pp!(values.get(k).map_or(-1, |&x| x as i64));
41            }
42            3 => {
43                pp!(seg.accumulate0(k));
44            }
45            4 => {
46                let count = seg.accumulate0(k);
47                pp!(if count == 0 {
48                    -1
49                } else {
50                    values[seg.partition_point_acc(count - 1)] as i64
51                });
52            }
53            5 => {
54                let count = seg.accumulate0(k);
55                let k = seg.partition_point_acc(count);
56                pp!(values.get(k).map_or(-1, |&x| x as i64));
57            }
58            _ => unreachable!(),
59        }
60    }
61}
Source

pub fn accumulate(&self, index: usize) -> u32

Returns the wrapping sum of 0..=index.

Source

pub fn fold(&self, left: usize, right: usize) -> u32

Returns the wrapping sum of left..right.

Source

pub fn get(&self, index: usize) -> u32

Source

pub fn fold_all(&self) -> u32

Source

pub fn partition_point_acc(&self, value: u32) -> usize

Returns the number of leading values whose inclusive prefix sum is at most value.

§Panics

Panics if a prefix sum has overflowed.

Examples found in repository?
crates/library_checker/src/data_structure/ordered_set.rs (line 39)
8pub fn ordered_set(reader: impl Read, writer: impl Write) {
9    prepare_io!(buffered; reader, writer);
10    sc!(n, q, a: [u32; n], queries: [(u8, u32); q]);
11    let mut values: Vec<_> = a
12        .iter()
13        .copied()
14        .chain(queries.iter().filter_map(|&(t, x)| (t <= 1).then_some(x)))
15        .collect();
16    values.radix_sort_by_key(|&x| x);
17    values.dedup();
18    let search = StaticSearch::from_sorted(&values);
19    let endpoints: Vec<_> = a
20        .into_iter()
21        .chain(
22            queries
23                .iter()
24                .map(|&(t, x)| if t == 3 || t == 4 { x + 1 } else { x }),
25        )
26        .collect();
27    let mut positions = vec![0; endpoints.len()];
28    search.lower_bound_batch(&endpoints, &mut positions);
29    let mut counts = vec![0; values.len()];
30    for &k in &positions[..n] {
31        counts[k] = 1;
32    }
33    let mut seg = DaryPrefixSumTreeU32::from_slice(&counts);
34    for ((t, x), &k) in queries.into_iter().zip(&positions[n..]) {
35        match t {
36            0 => seg.set(k, 1),
37            1 => seg.set(k, 0),
38            2 => {
39                let k = seg.partition_point_acc(x - 1);
40                pp!(values.get(k).map_or(-1, |&x| x as i64));
41            }
42            3 => {
43                pp!(seg.accumulate0(k));
44            }
45            4 => {
46                let count = seg.accumulate0(k);
47                pp!(if count == 0 {
48                    -1
49                } else {
50                    values[seg.partition_point_acc(count - 1)] as i64
51                });
52            }
53            5 => {
54                let count = seg.accumulate0(k);
55                let k = seg.partition_point_acc(count);
56                pp!(values.get(k).map_or(-1, |&x| x as i64));
57            }
58            _ => unreachable!(),
59        }
60    }
61}
Source

fn zeroed(len: usize, backend: SimdBackend) -> Self

Source

fn build(values: &[u32], backend: SimdBackend) -> Self

Source

fn add(&mut self, index: usize, value: u32)

Source

fn add_scalar(&mut self, index: usize, value: u32)

Source

unsafe fn add_avx2(&mut self, index: usize, value: u32)

Source

unsafe fn add_avx512(&mut self, index: usize, value: u32)

Source

fn partition_point_by<F>(&self, value: u32, first_gt: F) -> usize
where F: FnMut(&[u32; 16], u32) -> usize,

Source

fn partition_point_scalar(&self, value: u32) -> usize

Source

unsafe fn partition_point_avx2(&self, value: u32) -> usize

Source

unsafe fn partition_point_avx512(&self, value: u32) -> usize

Trait Implementations§

Source§

impl Clone for DaryPrefixSumTreeU32

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

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

Performs copy-assignment from source. Read more
Source§

impl Debug for DaryPrefixSumTreeU32

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

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> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

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 = !

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

fn try_from(value: U) -> Result<T, !>

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.