Struct SqrtDecomposition

pub struct SqrtDecomposition { /* private fields */ }

平方分割

Implementations

impl SqrtDecomposition

pub fn new(size: usize) -> Self

大きさsizeの列の平方分割の準備をする。

pub fn init(&self, init: impl FnMut(usize, Range<usize>))

各ブロックで初期化を施す。

pub fn block_num(&self) -> usize

分割したブロック数を返す。

pub fn query<F>(&self, range: Range<usize>, f: F)

where F: FnMut(usize, Range<usize>, Option<Range<usize>>),

rangeの範囲でのクエリを行う。

fには、ブロックの番号、ブロックの範囲、ブロックの部分クエリの範囲(Noneのときブロックの全体クエリ、Someのときブロックの部分クエリ)が与えられる。