Function alpha_k 

fn alpha_k(k: usize, n: usize) -> usize

Examples found in repository

crates/competitive/src/data_structure/static_range_product.rs (line 170)

    fn new(data: Vec<S::T>, level: usize) -> Self {
        let n = data.len();
        if n <= DIRECT_SIZE || level == 0 {
            return Self::Direct { data };
        }
        if level == 1 {
            return Self::Disjoint {
                table: DisjointSparseTable::new(data),
            };
        }
        let block_shift = scaled_block_shift(alpha_k(level - 1, n));
        let block_size = 1usize << block_shift;
        if block_size <= 1 || block_size >= n {
            return Self::Direct { data };
        }
        let blocks = block_products::<S>(&data, block_size);
        let between = Box::new(Self::new(blocks.products, level - 1));
        Self::Recursive {
            data,
            block_shift,
            prefix: blocks.prefix,
            suffix: blocks.suffix,
            between,
        }
    }

    #[inline]
    fn fold(&self, l: usize, r: usize) -> S::T {
        match self {
            Self::Direct { data } => fold_slice::<S>(data, l, r),
            Self::Disjoint { table } => table.fold(l, r),
            Self::Recursive {
                data,
                block_shift,
                prefix,
                suffix,
                between,
            } => {
                let block_shift = *block_shift;
                let bl = l >> block_shift;
                let br = (r - 1) >> block_shift;
                if bl == br {
                    return fold_slice::<S>(data, l, r);
                }
                let mut res = suffix[l].clone();
                if bl + 1 < br {
                    let mid = between.fold(bl + 1, br);
                    res = S::operate(&res, &mid);
                }
                S::operate(&res, &prefix[r - 1])
            }
        }
    }
}

#[inline]
fn fold_slice<S>(data: &[S::T], l: usize, r: usize) -> S::T
where
    S: SemiGroup,
{
    let mut res = data[l].clone();
    for x in &data[l + 1..r] {
        res = S::operate(&res, x);
    }
    res
}

fn block_products<S>(data: &[S::T], block_size: usize) -> BlockProducts<S::T>
where
    S: SemiGroup,
{
    let n = data.len();
    let mut prefix = data.to_vec();
    let mut suffix = data.to_vec();
    let mut products = Vec::with_capacity(n.div_ceil(block_size));
    for start in (0..n).step_by(block_size) {
        let end = n.min(start + block_size);
        for i in start + 1..end {
            prefix[i] = S::operate(&prefix[i - 1], &data[i]);
        }
        for i in (start..end - 1).rev() {
            suffix[i] = S::operate(&data[i], &suffix[i + 1]);
        }
        products.push(prefix[end - 1].clone());
    }
    BlockProducts {
        prefix,
        suffix,
        products,
    }
}

fn alpha_k(k: usize, n: usize) -> usize {
    if k == 0 {
        return n.div_ceil(2);
    }
    if n <= 1 {
        return 0;
    }
    let mut x = n;
    let mut c = 0;
    while x > 1 {
        x = alpha_k(k - 1, x);
        c += 1;
    }
    c
}

fn inverse_ackermann(n: usize) -> usize {
    let mut k = 0;
    while alpha_k(k, n) > 3 {
        k += 1;
    }
    k
}