Struct DaryPrefixSumTreeU64 

pub struct DaryPrefixSumTreeU64 {
    levels: Vec<Vec<PrefixBlock<u64, 8>>>,
    len: usize,
    total: u64,
    partition_valid: bool,
    backend: SimdBackend,
}

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<u64, 8>>>

len: usize

total: u64

partition_valid: bool

backend: SimdBackend

Implementations

impl DaryPrefixSumTreeU64

pub fn new(len: usize) -> Self

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

Examples found in repository

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 24)

pub fn vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
    let tree = XorLinkedRootedTree::builder(n)
        .with_dfs_preorder()
        .build_from_ordered_parents(p);
    let b: Vec<_> = tree.dfs_order().iter().map(|&v| a[v]).collect();
    let mut seg = DaryPrefixSumTreeU64::from_slice(&b);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { u, x } => seg.update(tree.dfs_index(u), x),
            Query::Sum { u } => {
                let range = tree.subtree_range(u);
                pp!(seg.fold(range.start, range.end));
            }
        }
    }
}

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

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

Adds value at index. Arithmetic is wrapping.

Examples found in repository

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

pub fn vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
    let tree = XorLinkedRootedTree::builder(n)
        .with_dfs_preorder()
        .build_from_ordered_parents(p);
    let b: Vec<_> = tree.dfs_order().iter().map(|&v| a[v]).collect();
    let mut seg = DaryPrefixSumTreeU64::from_slice(&b);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { u, x } => seg.update(tree.dfs_index(u), x),
            Query::Sum { u } => {
                let range = tree.subtree_range(u);
                pp!(seg.fold(range.start, range.end));
            }
        }
    }
}

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

Replaces the value at index. Arithmetic is wrapping.

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

Returns the wrapping sum of 0..end.

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

Returns the wrapping sum of 0..=index.

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

Returns the wrapping sum of left..right.

Examples found in repository

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 31)

pub fn vertex_add_subtree_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
    let tree = XorLinkedRootedTree::builder(n)
        .with_dfs_preorder()
        .build_from_ordered_parents(p);
    let b: Vec<_> = tree.dfs_order().iter().map(|&v| a[v]).collect();
    let mut seg = DaryPrefixSumTreeU64::from_slice(&b);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { u, x } => seg.update(tree.dfs_index(u), x),
            Query::Sum { u } => {
                let range = tree.subtree_range(u);
                pp!(seg.fold(range.start, range.end));
            }
        }
    }
}

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

pub fn fold_all(&self) -> u64

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

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

Panics

Panics if a prefix sum has overflowed.

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

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

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

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

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

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

fn partition_point_by<F>(&self, value: u64, first_gt: F) -> usize

where F: FnMut(&[u64; 8], u64) -> usize,

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

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

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

Trait Implementations

impl Clone for DaryPrefixSumTreeU64

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for DaryPrefixSumTreeU64

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

Formats the value using the given formatter.