BinaryIndexedTree 書いてみた話

なんか書かないと忘れちゃいそうなので。茶色の時に書けたし怖くないよ！でもいろいろ初心者なので間違ってたらどんどん言ってください！

BITについて

BinaryIndexedTree の略。
可換モノイド列 $a_0, a_1, \dots, a_{n -1}$ を乗せることができる。 (追記) モノイドは、二項演算できて結合法則満たして単位元があればよい。可換であるためには交換法則を満たせばよい。(追記)まあたぶんモノイドじゃなかったら乗せるときに気づきそう。
しかし逆元がないと prefix sum しか求められません。(追記)可変群を扱うことが多いでしょう

クエリ

$a_0, a_1, \dots a_{n - 1}$ に以下の二つのクエリがどちらも $O(log \ n)$ でできる。

$add(i, x)$ : $a_i \mathrel{{+}{=}} x$
$getsum(j)$ : $\displaystyle \sum_{k \in [0, j)} a_k$ を求める。

実装

ここ (Binary indexed tree) とかが強い。~~自分のブログで他人のスライド貼るのはどうなの~~
$a_0, a_1, \dots a_{n - 1}$ について、長さ $n$ の配列一個で表現できます。ただし、正確には長さ $n + 1$ になります。( 1-indexed のほうが嬉しいので)
理論の図は上のスライドを見てください。 TODO:書く~~(絶対やらねえ)~~

個人的な実装の話

実装は 1-indexed のほうが適しているので見かけ上 0-indexed っぽくなるようにしています。

$add(i, x)$
初めに $i \mathrel{{+}{=}} 1$ をし、1-indexed のお気持ちになる。
その後、 $LSB$ を足していき、木を上に登っていく。
$getsum(j)$
まず、 1-indexed にする。 $j \mathrel{{+}{=}} 1$ をする。半開区間 $[0, j)$ にそろえたいが実装上全開区間 $[0, j - 1$ ] のほうが都合がよいので、 $j \mathrel{{-}{=}} 1$ をする。
すると、結局のところ $j$ のままで OK。
なので $j$ から $LSB$ を引き、木を下がっていく。
なお、 $LSB$ は最下位 bit を指す。 $x \ bitwiseAND \ (-x)$ で求まるらしい。これ天才だろ。

BIT の実装例( C++ )

template<typename T>
//0-indexed/内部的に 1-indexed
struct BIT {
    vector<T> tree;
    //初期化
    BIT(ll n) : tree(n) {
        tree.assign(n + 1, 0);
    }

    //[0, n) の sum を返す/0-indexed
    T sum(ll n) {
        T ret = 0;
        //実は 1-indexed だが半開区間なので見た目がそのまま
        for (; n >= 0; n -= LSB(n)) {
            ret += tree[n];
            if (!n)break;
        }
        return ret;
    }

    //n 番目に x を足す
    void add(ll n, T x) {
        ll siz = tree.size();
        for (++n; n < siz; n += LSB(n))tree[n] += x;
    }
};

問題

RSQ( verify 用問題)
数列に対して加算と合計を聞くクエリにこたえる問題。
yosupo judge さん大好き！
judge.yosupo.jp AOJ 版( 1-indexed であることに注意) onlinejudge.u-aizu.ac.jp
ちなみに簡単な引き算で $[i, j)$ の合計は手に入る。

転倒数はバリ典型問題(以下に解法を載せます)

$a$ がとりうる値の長さ(制約より $N$ ) $+1$ の配列 $b_0, b_1, \dots, b_{N}$ を取り、 $b_i$ を $i$ の出現回数とすると、 $i$ の前にいくつ大きい数があったかが $getsum(i + 1, N)$ で出る。これをもとの配列すべてについて回せばよく、また $getsum(i + 1, N)$ を回す前後で $add(i)$ をすればよい。こうすることで今見ているところからの情報のみが得られる。
計算量は、クエリが $O(log \ n)$ , これを $n$ 回回すので $O(n \ log \ n)$ 。 atcoder.jp