小学生でもわかる累積和と中学生でもわかるBinary Indexed Tree

こんばんは、リューです。今日はテスト３日目でした。留年への新たな一歩を踏み出した気がします。 JOI予選も近いですし、今日は競技プログラミングでたまによく使われるアルゴリズムとデータ構造である累積和とBinary Indexed Tree（通称BIT)の考え方についてのお話をしようと思います。プログラミングを知らない方にも理解できることを目標に書きました。~~ただし、私の技量では小学生に説明できないので、計算量の詳細や実装のお話はしていません。~~サンプルコードを追加しました。その辺の話はググって調べてください。

序章

突然ですがこんな場合を想像してみたください。

あなたはよくA駅やB駅から電車に乗ります。A駅～J駅まであり、行先は様々ですが運賃は駅間ごとに決まっています。

ある日の駅間ごとの運賃は以下の通りでした。

A駅～B駅：118円
B駅～C駅：191円
C駅～D駅：410円
D駅～E駅：598円
E駅～F駅：129円
F駅～G駅：493円
G駅～H駅：334円
H駅～I駅：357円
I駅～J駅：432円

さて、ここで問題です。A駅からG駅まで行くための運賃は何円でしょうか？また、B駅からI駅まで行くための運賃は何円でしょうか？（コンピュータの気持ちになって計算してみましょう）

計算は終わりましたか？答えはA駅からG駅までが1939円、B駅からI駅までが2512円でした。計算する回数が多く少し面倒ですね。1度だけならいいですが何度も計算するとなると少し面倒です。また、これでは駅の数に比例して計算回数が増えるので、駅が1000万駅あると毎回平均約500万回、最悪1000万回計算しないといけません。

累積和

このままでは大変なので、あなたは考えて以下の表を作りました。

A駅～B駅： 118円
A駅～C駅： 309円
A駅～D駅： 719円
A駅～E駅：1317円
A駅～F駅：1446円
A駅～G駅：1939円
A駅～H駅：2273円
A駅～I駅：2630円
A駅～J駅：3062円

この表を使うことで、どこの駅へ行くにもすぐに運賃が求められます。それでだけでなく、B駅からある別の駅に行くにもA駅～B駅までの118円を引くことで1回の計算で運賃が求められます。B駅だけでなく、あらゆる一つの駅からもう一つの駅までの運賃も1回の計算で求めることができます。駅が1000万駅あっても1回だけで計算できます。先ほどより数百万倍速いです。すごいですね。（表を作るのに1000万回計算しないといけませんが）

このようにして、1番目～n番目までの値の総和をそれぞれnで記憶して、区間の値の総和を高速に求めるのが累積和の考え方です。

Binary Indexed Tree

しかし、累積和にもいいことばかりではありません。以下の場合を考えてみましょう。

ある時、電気代の値上げによりA駅～B駅間の運賃が10円値上げしました。1つめの表だとA駅からB駅までの運賃を10円加算すればいいだけですが、累積和の表ではA駅～B駅だけでなく、他の区間の運賃も書き換えないといけません。駅が少ないなら大丈夫かもしれませんが、1000万駅あれば1000万回書き換えです。大変ですね。

ここで登場するのがBinary Indexed Tree、通称BITです。BITは累積和と普通の方法の間を取ったような考え方です。少々奇妙に見えるかもしれませんが、以下の表をご覧ください。（10円はまだ足していません）

A駅～B駅(1駅間)： 118円
A駅～C駅(2駅間)： 309円
C駅～D駅(1駅間)： 410円
A駅～E駅(4駅間)：1317円
E駅～F駅(1駅間)： 129円
E駅～G駅(2駅間)： 622円
G駅～H駅(1駅間)： 334円
A駅～I駅(8駅間)：2691円
I駅～J駅(1駅間)： 432円

A番目の駅からn番目の駅には、2^m駅前からn番目の駅までの運賃の総和を記録しています。(mはn/(2^m)の余りが０となる最大の自然数)

例えば、1番目のB駅なら2⁰=1で割り切れるので1つ前のA駅からの運賃を記録

4番目のE駅なら2²=4で割り切れるので4つ前のA駅からの運賃を記録

6番目のG駅なら2¹=2で割り切れるので2つ前のE駅からの運賃を記録しています。

n番目までの総和を求める際は、nを二進数に変換し、最も末位の1を0にしながら足していきます。

例えば、7番目のG駅までなら、二進数に変換すると111Bとなり、111B(7)番目のG～H駅と110B(6)番目のE～G駅と100B(4)番目のA～E駅を足して求めることができます。

9番目のJ駅までなら、二進数に変化すると1001Bとなり、1001B(9)番目のI～J駅と1000B(8)番目のA～I駅を足して求めることができます。

12/3追記　divさんに図解していただきました。ご提供ありがとうございました！。

また、累積和と同様に引き算をすることで、あらゆる一つの駅からもう一つの駅までの運賃も簡単に求めることができます。

駅の数が少ないとむしろ効率が悪いように感じるかもしれませんが、BITなら駅が1000万駅に増えても加算、区間の総和の計算ともに約20回で計算できます。（表を作るには累積和などよりも少し多めに計算しないといけません）

このように、加算、区間の総和の計算ともにそこそこ優秀なのがBITの強みです。

さいごに

みなさん、累積和とBITについて理解いただけましたでしょうか？駄文で申し訳ありませんでしたが、少しでも累積和とBITを理解いただけたら幸いです。

明日、12/4のアドベントカレンダーはreanさんに書いてもらおうと思います。元会長のすばらしい記事に乞うご期待です。

サンプルソース

//累積和
#include <iostream>
using namespace std;
const int SIZE=1<<10;
int array[SIZE+1];
int cumsum[SIZE+1];//今回の実装では0番目は番兵にしています。
//番兵にしなくてもいいのですが、個人的にはこちらの方が直観的で書きやすいと思います。
int sum(int a,int b){//array[a]~array[b]までの総和を求めます
    if(a>=b)
        return 0;
    return cumsum[b]-cumsum[a-1];
}
void add(int a,int x){//一応加算できますが、O(n)と重く、加算するときはBITを使うのでたいてい書きません。
    for(int i=a;i<=SIZE;++i)
        cumsum[i]+=x;
}
int main() {
    for(int i=1;i<=SIZE;++i)//適当に配列を作ります
        array[i]=i;
    
    for(int i=1;i<=SIZE;++i)//累積和を求めていきます
        cumsum[i]=cumsum[i-1]+array[i];
    
    // your code goes here
    return 0;
}

//BIT
#include <iostream>
using namespace std;
const int SIZE=1<<10;//サイズは2の乗数じゃなくても構いません
int array[SIZE+1];
int BIT[SIZE+1];//0番目を番兵にしています
int sum(int a){
    int ans=0;
    while(a){
        ans+=BIT[a];
        int least=a&-a;//これで最も末位の1のビットを求めることができます。
        a-=least;
    }
    return ans;
}
int sum(int a,int b){//array[a]~array[b]までの総和を求めます
    if(a>b)
        return 0;
    return sum(b)-sum(a-1);
}
void add(int a,int x){//加算の方法は本文では説明しませんでした。最も末位の1のビットを繰り上げながら加算していきます。
    while(a<=SIZE){
        BIT[a]+=x;
        int least=a&-a;//sumのleastど同様
        a+=least;//leastの桁を繰り上げます。
    }
}
int main() {
    for(int i=1;i<=SIZE;++i)//適当に配列を作ります
        array[i]=i;
    
    for(int i=1;i<=SIZE;++i)//BITを求めていきます
        add(i,array[i]);
    // your code goes here
    return 0;
}

追記

12/3 Binary Indexed TreeがBinary Index Treeになっていたのを修正

同日サンプルソースを追加提供していただいた画像を追加 12/13 BITのサンプルソースが間違っていたのを修正