Struct nekolib::ds::disjoint_sparse_table::DisjointSparseTable

pub struct DisjointSparseTable<M: Monoid> { /* private fields */ }

disjoint sparse table。

要素数 $n$ の配列の任意の区間について、モノイド積の値を計算できる。 値の更新はできない。 半群を返すことにしてもよいが、要検討。

Idea

各 $k$ ($1\le k< \log_2(n)$) について、区間 $[i\cdot 2^k-j, i\cdot 2^k)$ および $[i\cdot 2^k, i\cdot 2^k+j)$ ($2\le j\le 2^k$、$i$ は区間の終端が $n$ 以下になる各奇数) におけるモノイド積を予め計算しておく。 任意の区間は、上記の区間を高々 $2$ つ合わせることで表現できる。

Implementation notes

前処理では、異なる段で同じ区間のモノイド積を複数回計算するのを避けるための工夫をしている。 その処理のオーバーヘッドにより、モノイド積のコストが高くない場合は、 毎回計算する方が高速かもしれない。クエリ処理についても同様の工夫をしている。

Complexity

演算	時間計算量
from	$\Theta(n\log(n))$
fold	$\Theta(1)$

Precise analysis

前処理におけるモノイド積の計算回数は以下の値で上から抑えられる。 $$n\cdot\lceil{\log_2(n)-3}\rceil + 2\cdot\lceil{\log_2(n)}\rceil + 2.$$

これは、$n = 1000$ で $7022$ であり、 Secret の「$n = 1000$ でクエリ $8000$ 回以下」に余裕を持って間に合う。

クエリ処理の際には、 与えられた区間が前処理で計算した区間であるか、長さが $1$ 以下の場合は、 新たにモノイド積は計算せずに答えを返す。 そうでない場合はちょうど $1$ 回のモノイド積を計算する。

More precise analysis

前処理の実際の計算回数は、以下のコードにより $O(\log(n))$ 時間で計算できるはず。 コード長が長いので隔離したいかも。

/// 要素数 `n` での前処理における計算回数を返す。
fn count(n: usize) -> usize {
    if n <= 2 {
        return 0;
    }
    g(n - 1)
        + if n.is_power_of_two() {
            n.trailing_zeros() as usize
        } else {
            n.next_power_of_two() / 2
        }
        - 1
}

assert_eq!(count(3), 1);
assert_eq!(count(10), 14);
assert_eq!(count(1000), 7008);
assert_eq!(count(1_000_000), 16_980_635);

/// 各段における寄与分の和を返す。
fn g(n: usize) -> usize {
    (0..)
        .take_while(|&k| n >= 2_usize.pow(k + 1))
        .map(|k| f(k, n - 2_usize.pow(k + 1)))
        .sum()
}

/// k 段目における寄与分を返す。
fn f(k: u32, n: usize) -> usize {
    let p = 2_usize.pow(k);
    n / (2 * p) * p
        + if n / p % 2 == 1 { n % p + 1 } else { 0 }
        + (n + 1) / (2 * p) * (p - 1)
}

Examples

use nekolib::ds::DisjointSparseTable;
use nekolib::traits::Fold;
use nekolib::utils::OpRollHash;

let op_rh = OpRollHash::<998244353>::default();
let value_of = |s| op_rh.value_of(s);

let base: Vec<_> = ["abra", "cad", "abra"].iter().map(|s| value_of(s)).collect();
let dst: DisjointSparseTable<_> = (base, op_rh).into();
assert_eq!(dst.fold(1..=2), value_of("cadabra"));
assert_eq!(dst.fold(..), value_of("abracadabra"));

Trait Implementations

impl<M, B> Fold<B> for DisjointSparseTable<M>where M: Monoid, M::Set: Clone, B: RangeBounds<usize>,

type Output = M

fn fold(&self, b: B) -> M::Set

r で指定される区間の和を返す。

impl<M> From<(Vec<<M as Magma>::Set, Global>, M)> for DisjointSparseTable<M>where M: Monoid, M::Set: Clone,

fn from((base, monoid): (Vec<M::Set>, M)) -> Self

Converts to this type from the input type.

impl<M> From<Vec<<M as Magma>::Set, Global>> for DisjointSparseTable<M>where M: Monoid + Default, M::Set: Clone,

fn from(base: Vec<M::Set>) -> Self

Converts to this type from the input type.

impl<M> Index<usize> for DisjointSparseTable<M>where M: Monoid, M::Set: Clone,

type Output = <M as Magma>::Set

The returned type after indexing.

fn index(&self, i: usize) -> &Self::Output

Performs the indexing (container[index]) operation.