BIT の定数倍高速化について

実装例

概要

BIT を用いて non-prefix な区間$ [s, t)の結果を$ {\rm fold}(t) \times {\rm inv}({\rm fold}(s - 1))などとして求めることができます．

今回はこの方法を用いずに区間$ {\rm fold}をすることで定数倍高速化をします．

方法

1.$ {\rm last} \le {\rm first}になるまで$ {\rm first}を左に寄せる．

2.$ {\rm first} \le {\rm last}になるまで$ {\rm last}を左に寄せる．

実装

code:cpp

value_type fold(size_type first, size_type last) {

value_type acc = value_structure::identity();

while(first < last) {

acc = value_structure::operation(datalast, acc);

last -= get_lsb(last);

}

while(last < first) {

acc = value_structure::operation(value_structure::inverse(datafirst), acc);

first -= get_lsb(first);

}

return acc;

}

証明

ひとつめのwhileが終わった段階での$ {\rm last}を$ {\rm last}'と書きます．　また，$ {\rm last}'に到達する直前に加えた区間の長さを$ Lとします．

このとき$ {\rm last}' \le {\rm first} \le {\rm last}' + Lが成り立ちます．　よって(last' >> L) == (first >> L)が成り立ちます（$ {\rm last}'の下$ \log(L) + 1桁は$ 0なので）．　また LSB を減じ続ける操作というのは，下の bit をどんどん$ 0にしていくという処理になります．　ゆえに$ {\rm first}の下$ \log(L) + 1桁がすべて$ 0になった時点でlast' == firstです．

$ [0, s)を幾分か処理しないので定数倍高速化になっています．