$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

◇◇tech006:BITで配列の区間加算と一点参照◇◇

☆概要

配列の区間加算一点参照は、BITを使えばlogオーダーでできる。

☆本文

区間加算区間参照ができるデータ構造として遅延評価セグ木があるが、一点参照でよければBITでできる。要領としてはimos法と同じで、L番目の要素からR番目の要素までに値valを加算したいとき、L番目の要素にvalを足してR+1番目の要素に-valを足せばよい。1-indexedであれば1番目の要素からM番目の要素までの和がO($\log N$)でとれるので、加算、参照ともにO($\log N$)である。

☆問題

戻る