Hatena::ブログ(Diary)

komiyamの日記

2013-12-02

Segment Treeをちょっと高速化したい

Competitive Programming Advent Calendar Div2013の12月2日の分です。

ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。

はじめに

segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです(定番中の定番ですね)。この資料で使われている図をイメージしながら読んでください。同じくiwiさんの平衡二分探索木のスライドもぜひ目を通しておきましょう。

これら以外にもsegment treeについてまとめたブログ記事などは検索すれば色々引っかかります。去年や今年のAdvent Calendarでも初学者向けの記事があるようです。初学者向けの詳しい解説はそちらをご覧ください。

私なりにsegment treeの動作原理を短くまとめると、「区間をたかだかO(log n)個の交わらない区間に分割する」で終わりです。余談ですが私の好きなデータ構造であるsparse tableの動作原理は「区間をたかだか定数個の交わりうる区間に分割する」とsegment treeとの対比が見られます。

定数倍最適化について

ところで、プログラミングコンテストというのはとにかく通れば正義です。逆もしかりで、「私はO(n)解法を考案しました」だけではスコアは増えません。それを実装して、TLEせずに通さなければ順位は上がらないのがプログラミングコンテストの面白さの一つだと思っています。

TLEせずに通すにあたって定数倍というのは結構大事で、もしこれを無視してよいのであればdoubleなんてfloat並の化石扱いで__float128使うし、座標圧縮でmap使ったらTLEしたとかよくあるし、逆では4重ループだけど係数1/24が乗るから行けた!とか4*10^9だから愚直は無理だなーと思ったら通ったとかあったりします。また想定解は累積和だけどbinary indexed treeでも通ったとか、しゃくとりするところを二分探索でlogがかかったけど行けたとかは頻繁にありますね。

私はあまり詳しく無いのですが、どうも計算時間で支配的になりがちなのはメモリアクセスだという話です。この問題とかは有名なようで。キャッシュに乗りやすくするようデータをコンパクトに保つことなども大事らしいです。平方分割がsegment treeに比べて思ったより遅くないのもメモリアクセスの効率の差なんですかね。

segment treeに話を戻しましょう。先ほど動作原理を「区間をたかだかO(log n)個の交わらない区間に分割する」と書きましたがこれだけなら平衡二分探索木を使って列を扱うのにもあてはまります。binary indexed treeも同じです。実際にこれらのデータ構造は諸々の処理に必要な計算量はどれも同じです。初期化O(n)、空間O(n)、点クエリや区間クエリO(log n)など。大雑把に言って、平衡二分探索木からinsert,delete,split,mergeなどができないよう制限したのがsegment treeで、segment treeの区間[L,R)に対するクエリをL=0に制限したのがbinary indexed treeだと見なすことができます。機能を制限した分だけ実装や速度やメモリの面で利点が得られるようになっています。

binary indexed tree

binary indexed treeはsegment treeから無駄なノードを削ったデータ構造です。その名の通り、二進表示と配列の番号が絶妙に対応付けられています。

計算量はO(log n)ですが、[0,n)というクエリに対して毎回コンスタントにlog n回必要ということもなく、二進表現で0が連続する箇所だとか1が連続する箇所だとかをまとめてスキップしたり、普通に書けば再帰を使わなくて済んだり、配列へのアクセスが昇順または降順で効率がよいことなどからかなり高速に処理できます。

元のデータと同じ長さの配列で済む(サイズを無理やり2のべきにする必要すら無い)というのが驚異的で、次元の上昇にも強いデータ構造です。

segment tree

コンテストでの使用頻度が高いsegment treeですが、当面は動的でないものを考えます。また、簡単のため扱うデータのサイズ(=:N)を2のべきにしておきます。

segment treeでは扱う木の形を完全二分木に限定しています。これにより各ノードについて配列インデックスが非常に沢山の情報を持つことになります。

特に子ノードや親ノードへのリンクを陽に持たなくてよいというのは空間的にかなりおいしいです。元データの2倍しかメモリ使わないというのは考えてみると結構すごい。

蟻本での実装とは異なりますが、配列を1-indexedで扱うことにします。配列の長さは2*Nで、0番目は使いません。そうすることで色々綺麗に扱えます。

iの親のindexi/2
iの子のindexi*2+0, i*2+1
iの兄弟(sibling)i^1
iの深さ(depth)log_2 iの整数部分
iの区間幅(width)N/highest(i)
iの区間の左端(i-highest(i))*width(i)
左からx番目の葉x+N

ここでhighest(i)はJavaでいうところのInteger.highestOneBit(i)のことでiを越えない最大の2べきで書ける数のことです。ビット演算を用いてO(log log n)で求めても良いしO(n)の前処理で求めておいてもよいです。

また、1,2,...,2*N-1がトポロジカル順序になっている点も美味しくつまり初期化は単純にループを後ろから回せば良いことになります。例えばRMQの場合

for(int i=0; i<N; ++i) minimum[i+N] = A[i];
for(int i=N-1; i>0; --i) minimum[i] = min(minimum[i*2+0], minimum[i*2+1]);

初期化できます。

xを含む区間のインデックスを下から順に列挙するには次の様に葉から親を辿ればよいです。

for (int i=x+N; i>0; i>>=1) {
    //iが対応するインデックス
}

[L,R)を分解した区間のインデックスを列挙するにはこう書きます。

L += N;
R += N;
for (;L<R; L>>=1, R>>=1) {
    if(R&1) --R; //--Rが対応するインデックス
    if(L&1) L++; //L++が対応するインデックス
}

実装量も再帰で書くより少なくなってよいですね。[L,R)を分解した区間は互いに交わらないのでどういう順番で列挙してもよいのですが、この方法ではインデックスの大きい順に列挙されていることも分かります。

何をやっているのかというと、[L,R)に対応するノードの山を真ん中でぶったぎって山の左側と右側に分けてごちゃごちゃやっているだけです。binary indexed treeの様に、i&(-i)で最右ビットを取り出せることを利用して連続する末尾の0をスキップする実装もあります。(上の実装と比べて早くなっているのかどうかはよく分かりません)

遅延型segment tree

例えば区間への更新や加算クエリと区間への求値クエリを両方サポートする必要がある時、値の伝播を遅延させるテクニックを用いるとうまくいくことがあります。この技法を遅延更新とか遅延評価とか遅延伝播とか呼ぶようです。英語だとLazy Propagationという表現をよく見かける気がします。実装の関数名ではpushとかpush_upとかpush_downとかupdateとかpropagateとかmergeとかlazyなどが使われているようでした。具体的に何ができるかといえば、例えば区間更新と区間加算と区間最小値と区間和を対数時間で処理できる列などが扱えます。遅延を使わなければならない、ということはあまりないのですが結構応用範囲が広いので多くの人に使われている印象を受けます。

この技法についての詳細はここでは触れませんが、これも再帰を展開をしてみたいところです。

上でやったように簡単に書くことは難しいです。[L,R)を分解した区間を取り出すだけではダメで、そのノードに必要な情報を伝播するために直上のノードも取り出す必要があるからです。とはいえ

  • あるノードを扱うとき、親ノードはpropagate済にしておく。
  • ノード以下に触るときは事前にpropagateしておく。
  • ノードが完全な状態になった後に子ノードの情報をmergeする。

くらいに気をつけておけば大丈夫です。またpropagateやmergeは順序さえ間違わなければやっといて損をすることはありません。

と、ここまで書いといて申し訳ないんですが公開しようとしていたコードにバグがありました。基本的な考え方としては共通する部分は上から下ってそれから山を左右に分けて左側で下って上って、右側で下って一番上まで上って…という感じでうまく行くはずなんですが何かがバグっているようです。近日中にバグとって追記しておきます。一番肝心な部分が公開できずに申し訳ないです。

後、再帰で実装する場合でもC++ならpropagateやmergeをinline化するだけで実行速度は大分変わります。

12月4日追記:不恰好ながら一応実装できたので公開します。まず、遅延なしのsegment treeだとこんな感じに区間に分割されます。山とか言っていたのは図を見て察してください。

................................
................................
........LLLLLLLLRRRRRRRR........
........................RRRR....
......LL....................RR..
.....L..........................

遅延なしだとこれらを列挙するだけでよいのですが、遅延ありだと下の*のついたノードでpropagate/mergeを行う必要があります。

&#42;*******************************
********************************
********LLLLLLLLRRRRRRRR********
....****................RRRR****
....**LL....................RR..
.....L..........................

たくさんあるように見えますが、上の方は一つの配列がカバーする区間が大きいので、ノード数としては対数個で収まっています。

図を見ると一目瞭然ですが、propagate/mergeが必要なノードは山の両裾のノードから親を辿ることで得られます。ちょっと恰好悪い方法ですが、配列に処理すべきノードインデックスを溜め込むことで再帰を展開してみます。まずはインデックスを溜め込むコード。

void getIndexes(int indexes[], int &len, int L, int R) {
    len = 0;
    for(int a=L?(N+L)/(L&-L)>>1:0, b=R?((N+R)/(R&-R)-1)>>1:0;;b>>=1){
        if(a==b){
            for(;a;a>>=1) indexes[len++] = a;
            break;
        }
        if(a>b) swap(a,b);
        indexes[len++] = b;
    }
}

難しそうなところだけ簡単に説明しておくと、(N+L)/(L&-L)というのは、左端がLかつ自身が右の子であるようなノードインデックスです。

最終的にsegment treeに対する区間操作は次のように書けます。

void func(int L, int R){
    static int indexes[128], len;
    getIndexes(indexes, len, L, R);
    for(int i=len-1; i>=0; --i) propagate(indexes[i]);
    for(L+=N,R+=N;L<R;L>>=1,R>>=1){
        if(R&1) doSomething(--R);
        if(L&1) doSomething(L++);
    }
    for(int i=0; i<len; ++i) merge(indexes[i]);
}

遅延なしのタイプに比べてあからさまに不恰好ではありますが、これで一応遅延型segment treeの再帰を展開することができました。

それから、実装次第ではmergeはしばしば省略できます。

それ以外のsegment tree

普通のsegment treeや遅延型segment tree以外にも、動的segment treeや永続segment treeなどの応用があります。

これらは子へのリンクや担当する区間に関する情報を陽に持つ点で普通のsegment treeとは異なります。この再帰を取り除いて高速化するのは難しいです。書いたこと無い方は一度動的segment treeを書いておくことをお勧めします。平衡二分探索木を書くのも平衡させる為の操作を除けばそんなに変わらないし、永続化も変更加えるときにコピーとるだけです。ただしiwiさんのスライドで紹介されている平衡二分探索木の実装は、葉のみに元データを乗せるタイプではなく、各ノードがある1点に関する情報とそのノードを根とする部分木(部分列に対応)全体の情報の2種類を保持しているという点でsegment treeとは若干異なります。

省メモリ版(ネタ)

以下Nが2のべきに限らないときのことを考えます。

1次元のsegment treeを普通に実装すると、元のデータサイズがNのとき最悪でおよそ長さ4*Nの配列が必要になります。この4というのが結構大きいのが気になります。これを減らすことを考えてみましょう。ただし子や親へのリンクは陽に持たないようにすることが前提です。

実は木の形を完全二分木に限定する必要は無くて、使う配列の長さは2*highest(N-1)+N個あれば足ります(例:蟻本の「Crane」)。要するにわざわざ配列の末尾に単位元を埋めこむ必要は無いというだけのことです。2*highest(N-1)+Nというのは最悪でおよそ3*Nだと思ってよいでしょう。

もっと減らすこともできます。

元のデータを2のべきの個数ごとに分解してそれぞれsegment treeを構成すると長さ2*Nの配列で足ります。気分的には平方分割に近いですね。各操作での計算量もO(log N)と変わりありません。

もっとも、そこまで空間を節約したいなら時間を犠牲にして平方分割(長さN+sqrt(N)で良い)を使うのが実用的でしょうけど。

おわり

去年書いたときは「来年はLPとグラフについて書きたいなー」と思っていたんですが今年は不勉強でした。書くネタがまだ決まってない方は是非ご検討ください。私は大喜びします。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

リンク元