競プロのライブラリ整理~BIT(Binary Indexed Tree)~ - Qiita

BIT上での二分探索(2020/05/20追加) 先日出たCodeforcesにおいてBIT上での二分探索が必要な問題(問題はこちら)があり二分探索は実装していなかったので、復習として実装することにしました。 BIT上では$a_1+a_2+…+a_i>=x$となる最小の$i$を$O(log{n})$で求めることができます(ただし、数列aの全要素が0以上)。 最小の$i$が5になる場合の二分探索の際の挙動は以下のようになります。 長い区間から順に辿っていってその区間を含めても合計が$x$未満の場合はその区間を含めて下の区間を探していきます。 これを繰り返して一番下の長さ1の区間までたどりついた時のインデックスの一つ隣が求める答えであるiになります。 C++によるBITの実装 以下はクラスの中は1-indexedで関数に与える引数は0-indexedでの実装になり、先ほどまでで説明した内容をそ