セグメントツリーのデータ位置とツリー位置の関係

Question

data_arrayのデータ位置とtree_arrayのデータ位置の間に何らかの関係があると思います。

int data[N]; 
int tree[M]; // lets M = 2^X-1, where X = nearest ceiling power of 2 to N; 

void build_segment_tree(); 

data []のn番目の値がtree []のi番目の値にマッピングされているとは思いますか？何か数学的な解決はありますか？

Answer 1

することもできます。例えば、セグメントツリーは、セグメント情報を に格納する能力のために使用されます。

Nの要素ツリーからセグメントツリーを作成する場合は、 と表示されます。ceil(log_2(N))+1レベルが必要です。そして、最後のレベルでは、 の長さの範囲または単一の要素がすべて見つかります。

これらの要素は、正確には（1-インデックス）2^ceil(log_2(N))~2^ceil(log_2(N))+N-1になります。

  [1-8] 
     /  \ 
    [1-4]  [5-8] 
    / \ / \ 
    [1-2][3-4] [5-6][7-8] 
    /\  /\  /\ /\ 
    [1][2] [3][4] [5][6] [7][8] 

---

1-11 
/ \ 
1-6 7-11 
1-3 4-6 7-9 10-11 
1-2 3 4-5 6 7-8 9 10 11 
1 2 4 5 7 8 

この答えは2つの要素のパワーのセグメントツリーに対してのみ有効です。

しかし、他の要素については、要素は必ずしも整理されていない。

だから、答えはそれらは、あなたがどんなformualitveルールを見つけることができない場合2.

の力ではありませんNのためにfalseになります。