BIT

「BinaryIndexedTree」の略。

（多くの場合は）区間和を高速に計算するデータ構造。（他の場合については後述）

累積和を簡単に書く目的で使うことが多いかも。なので累積和の問題をBITで解いてみるといい。

code:cpp

using namespace atcoder;

int main(){

fenwick_tree<int> BIT(10);//大きさ10のBITをつくる

BIT.add(0,1);//0番目に1を足す

cout << BIT.sum(0,1) << endl;//[0,1)の和を求める。（右端は含まない）

}

BITには整数、加算を乗せることが多いが、これ以外の演算を乗せることもできる。

例えば小数なども乗せることができるが、他にも足し算（和）ではなくxorなどを乗せることもできる。（xorを乗せる、というのはつまり区間xorを取得できるBITを作るということ）

乗る演算には条件がある。演算の逆演算ができることが条件。たとえば最小値（区間min）は乗らない。