樹状配列の原理分析と使用
25317 ワード
に質問
所与の集合Sは、N個の要素を含み、各要素は区間[1,1000]内であり、ユーザは2つのパラメータx,yを入力し、任意の区間[x,y]内でj<=k、出現する要素和を解く.
ツリー配列の原理解析
区間ツリー表示
区間ツリーの完全表現は以下の通りであり,全区間の情報を表現できるように2^(k−1)個のノードを多く作成する必要があるツリー満二叉木であることがわかる.
しかし、実は右の子の和は、減算によって得ることができます.すなわち、右の子=親ノード−左の子=親ノード−左の子=親ノード−左の子です.したがって、私たちの区間の木の中のすべての右の子は削除されます(ここでは削除と言いますが、実際にはその親ノードに統合されています).木2のように得ることができます.[x,x]で表されるすべてのノードが記録した区間情報は,親ノードに階層的に統合された.
右の子のノードがすべて削除されたツリーをよく分析すると、削除されたノードのインデックスは2の倍数で、0を除くことがわかります.例えばインデックス4,10のノードが削除されると、インデックス9のノードのみが保持され、インデックス9のノードは区間[3,3]に対応する.すべての集計情報を整理すると、次のように説明されます.
7保留8連結3、3保留9連結10連結4連結4連結1連結1連結11連結12連結5 13連結14連結6連結2連結2連結2連結0連結0保留
これで、すべてのインデックスが2の倍数の右の子が親ノードにマージされます.
ツリー配列の雛形
しかし、これらの削除されたノードを、検索可能なツリーのツリーに再構築するにはどうすればいいのでしょうか.私たちは振り返って上の文字の説明を見て、とても規則的な感じがしますか?右に揃えられた木のように?私達は文字の説明の合併の過程を結び付けて、木の2を再び調整して、木の3を得て、とても面白いでしょう、木の2は全体の右に位置合わせされました!!!これは想像に難くありません.私たちはすべての右の子供を父の結点に合併したからです.つまり、下から上へ、層ごとに右の子供を右に移動することに相当します.
ツリー2の構造をどのように表すかを啓発した.N個の数が定義されている場合,すべての右の子を統合した後,N個のノードだけですべての区間の和を求める情報を表現できることは容易である.
我々は再び[1,8]個の数をツリー3と統合して分析し,ここでは統合されたすべてのツリーノードを,以下に示すように番号付けし直す.
以前に得られた解析から,すべての偶数インデックスのノードが親ノードにマージされていることが分かったが,ここではそれぞれ2,4,6,8の位置でマージされている.
ツリー配列インデックス関係定義
問題は、加算、減算によって任意の区間の和を得るために、これらの区間の親子関係をどのように定義するかということです.??
インデックスを6とするノード解析では,区間が[5,6]の区間の和であることを示しているが,[1,6]の区間の和を得るにはインデックスを4とするノード,すなわち区間[1,4]の和を加える必要がある.従って式を得ることができる:s u m(1,6)=s u m(1,4)+s u m(5,6)+v a l u e(6)=i n d e x(4)+i n d e x(6)+v a l u e(6)sum(1,6)=sum(1,4)+sum(1,4)+sum(5,6)+value(6)=index(4)+index(6)+value(6)+value(6)+sum(1,6)=sum(1,4)+sum(5,6)+value(6)=index(6)=index(6)+index(6)+index(6)+index(6)+4)+index(6)+value(6)
なお、木2の結果に対応して、[5,6]区間結点の親結点は[5,8]であり、[5,8]の親結点は[1,8]であり、連結操作後、[5,6]区間の親結点は[1,8]であり、[1,4]区間の親結点も[1,8]である.
インデックス7のノード解析では,s u m(1,7)=s u m(1,4)+s u m(5,6)+s u m(5,6)+s u m(7)=i n d e x(4)+i n d e x(6)+v a l u e(7)sum(1,7)=sum(1,4)+sum(5,6)+sum(7)+sum(7)+index(4)+index(6)+index(6)+value(7)sum(1,7)=sum(1,4)+sum(5,6)+sum(7)+sum(7)+sum(7)=index(7)=index(7)=index(7)dex(4)+index(6)+value(7)
インデックス8の接点解析では,s u m(1,8)=s u m(1,4)+s u m(5,6)+s u m(7)+v a l u e(8)sum(1,8)=sum(1,4)+sum(5,6)+sum(7)+value(8)sum(1,8)=sum(1,4)+sum(5,6)+sum(7)+value(8)+sum(1,8)=sum(1,4)+sum(5,6)+sum(7)+value(8)...
最終的に、index(...)がツリーノードインデックスを表す式のように、すべての接頭辞と区間とインデックスの関係が得られます.一方、value(…)は、s u m(1,1)=v a l u e(1)=i n d e x(1)s u m(1,2)=i n d e x(1)=i n d e x(1)+v a l u e(2)=i n d e x(2)s u m(1,3)=i n d e x(2)+i n n d e x(3)+i n d e x(3)=i n d e x(2)+v a l u e(3)s u m(1,4)=i n d e x(2)+i n d e x(3)+v a l u e x(4)+v a l u e e(4)+v a l u(4(4)=i n n n d e x(4)+)=i n d e x(4)s u m(1,5) = i n d e x ( 4 ) + i n d e x ( 5 ) = i n d e x ( 4 ) + v a l u e ( 5 ) s u m ( 1 , 6 ) = i n d e x ( 4 ) + i n d e x ( 6 ) = i n d e x ( 4 ) + i n d e x ( 5 ) + v a l u e ( 6 ) s u m ( 1 , 7 ) = i n d e x ( 4 ) + i n d e x ( 6 ) + i n d e x ( 7 ) = i n d e x ( 4 ) + i n d e x ( 6 ) + v a l u e ( 7 ) s u m ( 1 , 8 ) = i n d e x ( 4 ) + i n d e x ( 6 ) + i n d e x ( 7 ) + v a l u e ( 8 ) = i n d e x ( 8 )\begin{aligned} sum(1,1) &= &value(1) &= index(1)\\sum(1,2) &= index(1) + &value(2) &= index(2)\\sum(1,3) &= index(2) + index(3) = index(2) + value(3)\\sum(1,4) &= index(2) + index(3) + &value(4) &= index(4)\\sum(1,5) &= index(4) + index(5) = index(4) + value(5)\\sum(1,6) &= index(4) + index(6) = index(4) + index(5) + value(6)\\sum(1,7) &= index(4) + index(6) + index(7) = index(4) + index(6) + value(7)\\sum(1,8) &= index(4) + index(6) + index(7) + &value(8) &= index(8)\end{aligned} sum(1,1)sum(1,2)sum(1,3)sum(1,4)sum(1,5)sum(1,6)sum(1,7)sum(1,8)==index(1)+=index(2)+index(3)=index(2)+value(3)=index(2)+index(3)+=index(4)+index(5)=index(4)+value(5)=index(4)+index(6)=index(4)+index(5)+value(6)=index(4)+index(6)+index(7)=index(4)+index(6)+value(7)=index(4)+index(6)+index(7)+value(1)value(2)value(4)value(8)=index(1)=index(2)=index(4)=index(8)
上の式を分析し、木の構造を結合することで、8つの数、合計8つの木の結点があり、木の高さは4で、2つの面白い結論を得ることができます.インデックスが2のべき乗次ノードの接頭辞和は,前2^(k−1)個数の和,すなわちsum([1,8])=index(8) である.非2べき乗のノード接頭辞和は、sum([1,7])=index(4)+index(6)+index(7)のような複数のより小さく、それに等しいノードの組合せから得ることができ、これが動的計画思想の解法である.
上記の2つの興味深い結論は,接頭辞和に基づいて任意の区間の和を求めるのに役立ち,時間複雑度はO(logn)である.
ツリー配列の接頭辞和の解
接頭辞の和を求める問題を引用して、1つのインデックスNを与えて、前のN個の数の和を得ることを望んで、私達はどのようにするべきですか?N=7と仮定すると,上記の結論からsum([1,7])を求めるためには,まずindex(4),index(6),index(7)を知るべきであるが,与えられたインデックス番号7に基づいて関連するそのサブ問題インデックス番号4,6,7をどのように導出するか.
ここでは,下位LOWBIT(n)技術の導入が必要となる.
LOWBIT(n) = n & ( -n)
GOOGLEに関する概念では、ここでは簡単にその意味を説明することができます.nを1つ与え、その最低位が1の位置iを見つけ、1を左にシフト(i-1)した結果、すなわち(1<<尾0の数)を返します.
そこでLOWBIT関数を利用すると,7−L−LOWWIT(7)=7−1=6−6−LOWIT(6)=6−6−6−2=4−4−LOWIT(4)=4−4−4=0 7−LOWBIT(7)=7−1=6\6−LOWBIT(6)=6−2=4\4−LOWBIT(4)=4−4=4−4=0 7−LOWBIT(7)=7−1=66−LOWBIT(6)=6−6−2=6=4\4\4\4−LOWWBIT(4)=4−LOWWBIT(7=7−1=66−LOWWWBIT(6)=LOWBIT(4)=4−4=0
再帰的に現在のインデックスNを問い合わせることができ、加算すべきサブインデックスであり、疑似コードは以下の通りである.
任意の区間と
前述の方法では,入力されたインデックス番号Nに基づいて,接頭辞和,[1,N]の和のみを簡単に求めることができる.任意の区間,すなわち[x,y]の和をどのように解くか.
簡単です.getSum関数を2回2回呼び出して、差を求めればいいです.偽コードは以下の通りです.
ツリー配列の更新
前は固定配列のクエリー操作に対してのみ、更新操作が避けられないが、更新の過程は、クエリー過程の逆過程、すなわち1つのサブノードの値を与えて、どのように親ノードを更新するのか??
たとえば、数値2を指定すると、2を含むすべての区間の統計をどのように更新すればいいのでしょうか.2の親ノードは4で、祖先ノードは8、16...であることを知っています.そのため、偽コードは次のようになります.
まとめ
前述の説明では,自分の樹状配列を構築して解くことができるはずであるが,接頭辞和の区間問題に基づいて,線分木や区間木よりも構造的,操作的に簡単であるが,その使用には限界があり,区間木に完全に取って代わることはできない.
所与の集合Sは、N個の要素を含み、各要素は区間[1,1000]内であり、ユーザは2つのパラメータx,yを入力し、任意の区間[x,y]内でj<=k、出現する要素和を解く.
ツリー配列の原理解析
区間ツリー表示
区間ツリーの完全表現は以下の通りであり,全区間の情報を表現できるように2^(k−1)個のノードを多く作成する必要があるツリー満二叉木であることがわかる.
1：
(0)
[1,8]
(1) (2)
[1,4] [5,8]
(3) (4) (5) (6)
[1,2] [3,4] [5,6] [7,8]
(7) (8) (9) (10) (11) (12) (13) (14)
[1,1] [2,2] [3,3] [4,4] [5,5] [6,6] [7,7] [8,8]
しかし、実は右の子の和は、減算によって得ることができます.すなわち、右の子=親ノード−左の子=親ノード−左の子=親ノード−左の子です.したがって、私たちの区間の木の中のすべての右の子は削除されます(ここでは削除と言いますが、実際にはその親ノードに統合されています).木2のように得ることができます.[x,x]で表されるすべてのノードが記録した区間情報は,親ノードに階層的に統合された.
2：
(0)
[1,8]
(1) (2)
[1,4] [x,x]
(3) (4) (5) (6)
[1,2] [x,x] [5,6] [x,x]
(7) (8) (9) (10) (11) (12) (13) (14)
[1,1] [x,x] [3,3] [x,x] [5,5] [x,x] [7,7] [x,x]
右の子のノードがすべて削除されたツリーをよく分析すると、削除されたノードのインデックスは2の倍数で、0を除くことがわかります.例えばインデックス4,10のノードが削除されると、インデックス9のノードのみが保持され、インデックス9のノードは区間[3,3]に対応する.すべての集計情報を整理すると、次のように説明されます.
7保留8連結3、3保留9連結10連結4連結4連結1連結1連結11連結12連結5 13連結14連結6連結2連結2連結2連結0連結0保留
これで、すべてのインデックスが2の倍数の右の子が親ノードにマージされます.
ツリー配列の雛形
しかし、これらの削除されたノードを、検索可能なツリーのツリーに再構築するにはどうすればいいのでしょうか.私たちは振り返って上の文字の説明を見て、とても規則的な感じがしますか?右に揃えられた木のように?私達は文字の説明の合併の過程を結び付けて、木の2を再び調整して、木の3を得て、とても面白いでしょう、木の2は全体の右に位置合わせされました!!!これは想像に難くありません.私たちはすべての右の子供を父の結点に合併したからです.つまり、下から上へ、層ごとに右の子供を右に移動することに相当します.
3：
(0)
[1,8]
(1) (2)
[1,4] [x,x]
(3) (4) (5) (6)
[1,2] [x,x] [5,6] [x,x]
(7) (8) (9) (10) (11) (12) (13) (14)
[1,1] [x,x] [3,3] [x,x] [5,5] [x,x] [7,7] [x,x]
ツリー2の構造をどのように表すかを啓発した.N個の数が定義されている場合,すべての右の子を統合した後,N個のノードだけですべての区間の和を求める情報を表現できることは容易である.
我々は再び[1,8]個の数をツリー3と統合して分析し,ここでは統合されたすべてのツリーノードを,以下に示すように番号付けし直す.
： [1,8]
： [1,4] [x,x]
： [1,2] [x,x] [5,6] [x,x]
：[1,1] [x,x] [3,3] [x,x] [5,5] [x,x] [7,7] [x,x]
： (1) (2) (3) (4) (5) (6) (7) (8)
以前に得られた解析から,すべての偶数インデックスのノードが親ノードにマージされていることが分かったが,ここではそれぞれ2,4,6,8の位置でマージされている.
ツリー配列インデックス関係定義
問題は、加算、減算によって任意の区間の和を得るために、これらの区間の親子関係をどのように定義するかということです.??
インデックスを6とするノード解析では,区間が[5,6]の区間の和であることを示しているが,[1,6]の区間の和を得るにはインデックスを4とするノード,すなわち区間[1,4]の和を加える必要がある.従って式を得ることができる:s u m(1,6)=s u m(1,4)+s u m(5,6)+v a l u e(6)=i n d e x(4)+i n d e x(6)+v a l u e(6)sum(1,6)=sum(1,4)+sum(1,4)+sum(5,6)+value(6)=index(4)+index(6)+value(6)+value(6)+sum(1,6)=sum(1,4)+sum(5,6)+value(6)=index(6)=index(6)+index(6)+index(6)+index(6)+4)+index(6)+value(6)
なお、木2の結果に対応して、[5,6]区間結点の親結点は[5,8]であり、[5,8]の親結点は[1,8]であり、連結操作後、[5,6]区間の親結点は[1,8]であり、[1,4]区間の親結点も[1,8]である.
インデックス7のノード解析では,s u m(1,7)=s u m(1,4)+s u m(5,6)+s u m(5,6)+s u m(7)=i n d e x(4)+i n d e x(6)+v a l u e(7)sum(1,7)=sum(1,4)+sum(5,6)+sum(7)+sum(7)+index(4)+index(6)+index(6)+value(7)sum(1,7)=sum(1,4)+sum(5,6)+sum(7)+sum(7)+sum(7)=index(7)=index(7)=index(7)dex(4)+index(6)+value(7)
インデックス8の接点解析では,s u m(1,8)=s u m(1,4)+s u m(5,6)+s u m(7)+v a l u e(8)sum(1,8)=sum(1,4)+sum(5,6)+sum(7)+value(8)sum(1,8)=sum(1,4)+sum(5,6)+sum(7)+value(8)+sum(1,8)=sum(1,4)+sum(5,6)+sum(7)+value(8)...
最終的に、index(...)がツリーノードインデックスを表す式のように、すべての接頭辞と区間とインデックスの関係が得られます.一方、value(…)は、s u m(1,1)=v a l u e(1)=i n d e x(1)s u m(1,2)=i n d e x(1)=i n d e x(1)+v a l u e(2)=i n d e x(2)s u m(1,3)=i n d e x(2)+i n n d e x(3)+i n d e x(3)=i n d e x(2)+v a l u e(3)s u m(1,4)=i n d e x(2)+i n d e x(3)+v a l u e x(4)+v a l u e e(4)+v a l u(4(4)=i n n n d e x(4)+)=i n d e x(4)s u m(1,5) = i n d e x ( 4 ) + i n d e x ( 5 ) = i n d e x ( 4 ) + v a l u e ( 5 ) s u m ( 1 , 6 ) = i n d e x ( 4 ) + i n d e x ( 6 ) = i n d e x ( 4 ) + i n d e x ( 5 ) + v a l u e ( 6 ) s u m ( 1 , 7 ) = i n d e x ( 4 ) + i n d e x ( 6 ) + i n d e x ( 7 ) = i n d e x ( 4 ) + i n d e x ( 6 ) + v a l u e ( 7 ) s u m ( 1 , 8 ) = i n d e x ( 4 ) + i n d e x ( 6 ) + i n d e x ( 7 ) + v a l u e ( 8 ) = i n d e x ( 8 )\begin{aligned} sum(1,1) &= &value(1) &= index(1)\\sum(1,2) &= index(1) + &value(2) &= index(2)\\sum(1,3) &= index(2) + index(3) = index(2) + value(3)\\sum(1,4) &= index(2) + index(3) + &value(4) &= index(4)\\sum(1,5) &= index(4) + index(5) = index(4) + value(5)\\sum(1,6) &= index(4) + index(6) = index(4) + index(5) + value(6)\\sum(1,7) &= index(4) + index(6) + index(7) = index(4) + index(6) + value(7)\\sum(1,8) &= index(4) + index(6) + index(7) + &value(8) &= index(8)\end{aligned} sum(1,1)sum(1,2)sum(1,3)sum(1,4)sum(1,5)sum(1,6)sum(1,7)sum(1,8)==index(1)+=index(2)+index(3)=index(2)+value(3)=index(2)+index(3)+=index(4)+index(5)=index(4)+value(5)=index(4)+index(6)=index(4)+index(5)+value(6)=index(4)+index(6)+index(7)=index(4)+index(6)+value(7)=index(4)+index(6)+index(7)+value(1)value(2)value(4)value(8)=index(1)=index(2)=index(4)=index(8)
上の式を分析し、木の構造を結合することで、8つの数、合計8つの木の結点があり、木の高さは4で、2つの面白い結論を得ることができます.
上記の2つの興味深い結論は,接頭辞和に基づいて任意の区間の和を求めるのに役立ち,時間複雑度はO(logn)である.
ツリー配列の接頭辞和の解
接頭辞の和を求める問題を引用して、1つのインデックスNを与えて、前のN個の数の和を得ることを望んで、私達はどのようにするべきですか?N=7と仮定すると,上記の結論からsum([1,7])を求めるためには,まずindex(4),index(6),index(7)を知るべきであるが,与えられたインデックス番号7に基づいて関連するそのサブ問題インデックス番号4,6,7をどのように導出するか.
ここでは,下位LOWBIT(n)技術の導入が必要となる.
LOWBIT(n) = n & ( -n)
GOOGLEに関する概念では、ここでは簡単にその意味を説明することができます.nを1つ与え、その最低位が1の位置iを見つけ、1を左にシフト(i-1)した結果、すなわち(1<<尾0の数)を返します.
そこでLOWBIT関数を利用すると,7−L−LOWWIT(7)=7−1=6−6−LOWIT(6)=6−6−6−2=4−4−LOWIT(4)=4−4−4=0 7−LOWBIT(7)=7−1=6\6−LOWBIT(6)=6−2=4\4−LOWBIT(4)=4−4=4−4=0 7−LOWBIT(7)=7−1=66−LOWBIT(6)=6−6−2=6=4\4\4\4−LOWWBIT(4)=4−LOWWBIT(7=7−1=66−LOWWWBIT(6)=LOWBIT(4)=4−4=0
再帰的に現在のインデックスNを問い合わせることができ、加算すべきサブインデックスであり、疑似コードは以下の通りである.
getSum(N):
int ret = 0;
for i = N if i > 0:
// index(i) i
ret += index(i)
i -= LOWBIT(-i)
return ret
任意の区間と
前述の方法では,入力されたインデックス番号Nに基づいて,接頭辞和,[1,N]の和のみを簡単に求めることができる.任意の区間,すなわち[x,y]の和をどのように解くか.
簡単です.getSum関数を2回2回呼び出して、差を求めればいいです.偽コードは以下の通りです.
// x <= y， [x, y]
getSum(x, y):
return getSum(x-1) - getSum(y)
ツリー配列の更新
前は固定配列のクエリー操作に対してのみ、更新操作が避けられないが、更新の過程は、クエリー過程の逆過程、すなわち1つのサブノードの値を与えて、どのように親ノードを更新するのか??
たとえば、数値2を指定すると、2を含むすべての区間の統計をどのように更新すればいいのでしょうか.2の親ノードは4で、祖先ノードは8、16...であることを知っています.そのため、偽コードは次のようになります.
update(N, MAX):
for i = N if i <= MAX:
index(i) += N;
i += LOWBIT(i)
まとめ
前述の説明では,自分の樹状配列を構築して解くことができるはずであるが,接頭辞和の区間問題に基づいて,線分木や区間木よりも構造的,操作的に簡単であるが,その使用には限界があり,区間木に完全に取って代わることはできない.