セグメントツリーの配列サイズデータ構造

Question

セグメントツリーでは、セグメントツリーを配列の上に構築します。
たとえば、配列サイズが8 [0-7]の場合は、インデックス付けされます。セグメントツリー内のノードの
数は15、すなわち、第一、第二、第三、第四levls


でしかし、問題では1,2,4,8、私はseg tree[2*N + 1]として構造体配列のサイズを宣言した場合、そのが間違って与えています私がそれを以下のように宣言すれば答えます。

struct seg{ 
int sum; 
}; 
seg tree[4*N + 1]; 

それは間違った答えです。私の疑いは、[2 * N]で十分だということです。それでなぜそれが間違った答えを出すのですか？
番号9、親はそう左の子が2番号4であるた有するノードセグメント（1-1）* N右の子はnは、初期配列の大きさとする2 * N + 1

Answer 1

あります。セグメントツリーのサイズは次のようになります。2.

2*2^(log_2(n)+1)-1の力がある

• 2*n-1n場合nは2

編集の力ではない場合：それは私たちができることは事実です理論的にはツリーを作成するには、サイズ2*n-1の配列を作成しますが、セグメントツリーの配列表現では、親から子にどのように進むことができるか考えてください。左の子はインデックス2*i+1（0ベースのインデックス作成）になり、右の子はインデックス2*i+2になります。この不変量を維持するためには、完全なバイナリツリーを構築しなければならず、そのためには上記の式が述べられています。

thisを参照することもできます。