Hatena::Grouptopcoder

横道にそれるTopCoder参加記録でもいいじゃないか

 | 

2015-02-18要素数が2のべき乗ではないSegment Tree

komiyamさんのブログ( http://d.hatena.ne.jp/komiyam/20131202/1385992406 )を参考にしてSegment Treeを書いていたところ、実装を間違えたのにテストが通ってしまったところから、どうも要素数を2のべき乗でなくてもそのまま動作することに気づいた。


素数は2のべき乗でなくてもいいのか?

考察してみたところ、問題なさそうなことがわかった。


■格納領域は重複しないか?

Nは2のべき乗とは限らない任意の自然数とする。

素数Nの配列src[0]..src[N-1]を

素数N*2の配列dataのdata[N]..data[N*2-1]に格納する。


data[k] の親ノードは data[floor(k/2)]

data[k] の子ノードは data[k*2+0] と data[k*2+1]

とする。floor()は小数点以下の切り捨て。


するとNの偶奇によらず floor((N*2-1)/2) < N だから、

末尾のデータdata[N*2-1]の親ノードdata[floor((N*2-1)/2)]と、先頭のデータdata[N]が交差することはない。


また、N' = floor(N/2) とすると、floor((N*2-1)/2) <= N'*2 - 1 だから、

ノードと親ノードの親ノードの関係についても再帰的に交差がないことが保証できる。


■親ノードに格納された値は正しいか?

もとの配列src[0]..src[6]の7要素だとすると、


data[0] は使わない


data[1] = data[2] とdata[3]の親 (data[2]が想定外で正しくない)

data[2] = data[4] とdata[5]の親


data[3] = data[6]とdata[7]の親 (data[6]が想定外で正しくない)

data[4] = data[8]とdata[9]の親

data[5] = data[10]とdata[11]の親

data[6] = data[12]とdata[13]の親


data[7] = src[0]

data[8] = src[1]

data[9] = src[2]

data[10] = src[3]

data[11] = src[4]

data[12] = src[5]

data[13] = src[6]


といったように親ノードに格納された値は正しくないこともある。


■正しくない値の親ノードは使われるのか?

上記の例では

data[3] は src[-1], src[0]

data[1] は src[-3], src[-2], src[-1], src[0]

といったように、正しくない親ノード実在しないリーフノードを参照している。


ノードは、そのすべての子ノードが範囲クエリーに含まれる場合のみ利用されるため、

正しくない親ノードの値が使われることはない。


また正しくない値のノードが、正しくあるべきノードの値を上書きすることはない。

(正しくあるべきノードの子ノードはすべて実在のリーフノードを参照しているから、子ノードからの更新で不正な値に更新されることはない)


以上の理由により、以下のように配列を2のべき乗に拡張せずに使っても問題ないようだ。


#include <vector>

using namespace std;

struct SegTree{
    vector<int> data_;
    static int operation(int op1, int op2){
        return op1 + op2;
    }
    SegTree(const vector<int>& src){
        data_.resize(src.size() * 2);
        for(size_t i = 0; i < src.size(); i++) update(i, src[i]);
    }
    int query(size_t begin, size_t end, int init) const{
        begin += data_.size()/2; end += data_.size()/2;
        for(; begin < end; begin /= 2, end /= 2){
            if(begin & 1) init = operation(init, data_[begin++]);
            if(end & 1) init = operation(init, data_[end-1]);
        }
        return init;
    }
    void update(size_t pos, int val){
        pos += data_.size()/2;
        data_[pos] = val;
        while((pos /= 2) > 0){
            data_[pos] = operation(data_[pos*2], data_[pos*2+1]);
        }
    }
};

#include <algorithm>
#include <random>
#include <iostream>
#include <cassert>
using namespace std;
mt19937 rand_gen(123123123);

int main(){
    int width = 999999;
    vector<int> v(width);
    for(int i = 0; i < width; i++){
        v[i] = rand_gen() % 1000;
    }
    SegTree seg(v);
    for(int t = 0; t < 10000; t++){
        int left = rand_gen() % width;
        int right = rand_gen() % width;
        if(right < left) swap(left, right);
        int ans1 = seg.query(left, right, 0);
        int ans2 = 0;
        for(int j = left; j < right; j++){
            ans2 += v[j];
        }
        cerr << left << ", " << right << ", " << ans1 << ", " << ans2 << endl;
        assert(ans1 == ans2);
    }
    return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/machy3/20150218
 |