せでぃのブログ

ブログ初心者おいどんのどうでもいい愚痴やどうでもいい愚痴やどうでもいいマメ知識などを披露するチラシの裏です。

セグメント木の累積和できた

f:id:Sediment:20150114025254p:plain
 課題とコードはこの辺。
csny/segment-tree · GitHub
segment-tree/main.m at master · csny/segment-tree · GitHub
 前回頓挫してたのはこんな感じ。
セグメント木の累積和が上手くいかんなぁ - せでぃのブログ


 前回解決しきれなかったコードを眺めてて、コイン両替問題と同じ、経路探索であることに気づいて、幅優先探索でやってみた。幅優先探索は、構造上、何も考えんと最短経路を出すから助かる。答えは間違いなく出すけど、最適なコードかどうかはわかりませんw 流れはこんな。

  1. セグメント木の累積和、セグメント木の区間幅、セグメント木の開始番号の配列を3つ用意する
  2. 累積和用のキューと番号の飛び方のキューを用意する
  3. もし飛び方キュー(最初は開始番号)が終了番号と合致していれば答えを出力してループ終了
  4. もし飛び方キューに次の区間幅を加えても終了番号に届かなければ処理に移り、オーバーしていたら何もしない
  5. 開始番号に合致するかセグメント木をifで検索し、合致しなければ何もしない
  6. 合致したら累積和のキューに累積和を加え、番号の飛び方キューに区間幅を加えて3へ


 セグメント木はいろいろ融通が利いて便利だけど、補助的な配列が多くて結構疲れた。セグメント木の補助的な要素の求め方は、この辺で助けてもらいました。このボリュームのコードでも疲れましたわ。時間制限ありでやるのは辛そう。

Segment Treeをちょっと高速化したい - komiyamの日記

補助的な配列

 経路探索にもっていくには、経路のコスト(区間幅)と開始または終了位置が必要になる。
 2を底とする対数を使って上から0,1,2,3と階層を出し、その階層を使って16を2の累乗で割ると区間幅が出る。開始番号は適当に。
 Objective-CではhighestOneBitという関数が見つからなくてこんな感じになりました。

// セグメント木のセグメント区間幅[0][0-30]と区間の開始番号[1][0-30]
int treeattr[2][TOTALNUM*2-1];


// セグメント木作成
void init_tree(){
    for (int i=TOTALNUM-2;i>=0;i--){
        if (tree[i]==-1){
            tree[i]=tree[i*2+1]+tree[i*2+2];
        }
    }
    
    // 区間幅と開始番号の配列treeattr初期化
    int treewidth=TOTALNUM;
    for (int i=TOTALNUM*2-2;i>=0;i--){
        // セグメント木の区間幅
        // 2を底とするi+1の対数の整数部分が階層。上から0,1,2となる。
        double result1 = log2(i+1);
        // 16を2の累乗で割る
        int result2 = pow(2, floor(result1));
        treeattr[0][i]=TOTALNUM/result2;
        
        // セグメント木の区間の開始番号
        treeattr[1][i]=treewidth-treeattr[0][i]+1;
        treewidth -= treeattr[0][i];
        if (treewidth == 0){
            treewidth = TOTALNUM;
        }
    }
}

本題

 累積和を格納するキューと番号の飛び方を格納するキュー、ついでに経路表示用の文字の配列を用意して、FIFOの定型に入れる。

// start番目の番号からgoal番目までの累積和と計算回数を表示する
/* Queue  First-In First-Out方式 */
const int SIZE = 500; // キューとして使う配列のサイズ
// [0][i]累積和のキュー[1][i]番号の計算キュー
int queue[2][SIZE];
NSString *path[SIZE]; // 経路出力用に文字列の配列を用意

// 幅優先探索で、開始番号start=rから終了番号goal=s+1までの累積和を表示する
// 探索の根幹は#1.2.3.4.5のループ
void sum_sequence( int start, int goal ){
    // キュー入出力用に使う変数。frontは先頭、rearは末尾。
    // rearは次のノードの取り込み位置、frontは親ノード兼次の削除位置として利用。
    int rear = 1, front = 0;
    queue[0][front]=0; // 累積和の最初の親ノード
    queue[1][front]=start; // 番号の一番最初の親ノード
    path[front]=@"経路";
    while( front < rear ){ // #0.ループ設定 front=rearはキューが空の状態を表す
        for(int i = 0; i < TOTALNUM*2-1; i++){ // #1.子ノード取り込み処理開始
            if(queue[1][front]==goal){ // #2.条件判定等の処理
                // 探索結果出力
                NSLog(@"%d",queue[0][front]);
                NSLog(@"%@",path[front]);
                //NSLog(@"%@",path[rear]);
                return; // キューのサイズが足りないので、答えが出たら探索途中でwhileループ終了
            }else if(queue[1][front] + treeattr[0][i]<=goal){
                if(queue[1][front]==treeattr[1][i]){
                    queue[0][rear] = queue[0][front] + tree[i]; // #3.キュー取り込み
                    queue[1][rear] = queue[1][front] + treeattr[0][i];
                    path[rear]=[NSString stringWithFormat:@"%@,%d",path[front],tree[i]];
                    rear++; // #4.キューに取り込んだら、次に取り込む位置に移動
                }
            } // キューサイズ節約のため、startがgoalより大きくなったらキューに取り込まない
        }
        front++; // #5.キューの先頭の枝1本を探索済み・削除扱いして、次の枝の取り込みへ
    }
}