私は最近、セグメント ツリーと呼ばれる新しいデータ構造に出会い、2 次元にも拡張できることを読みましたが、その実装やその他の詳細について読むための適切な情報源を見つけることができませんでした。グラフィックの分野ではなく、プログラミングコンテストで使用するという観点から学びたいと思います。それを使用して解決できるいくつかの問題も役立ちます。誰かがそれについて読むための良い情報源を教えてくれませんか? ありがとう
3 に答える
2
特にプログラミング コンテストでは、セグメント ツリーを複数の次元に拡張することは、非常に困難で時間がかかる場合があります。
複数の次元が必要な場合は、まずバイナリ インデックス ツリーについて学習し、次にそれらを複数の次元に拡張してみてください。
バイナリ インデックス ツリーは、場合によってはセグメント ツリーよりも優れたパフォーマンスを発揮するデータ構造ですが、他の場合には単に不適切です。
セグメント ツリーを使用する場合、多次元への拡張は簡単です。
ここでは、それらに関する記事を見つけることができます。
ここでは、実装のテストに役立つ問題を見つけることができます。
于 2013-02-10T15:20:04.383 に答える
1
1D セグメント ツリーとその 2D 一般化について、コード サンプルを使用した優れた記事があります。しかし、それはロシア語なので、おそらくコードサンプルのみを考慮する必要があります=)
于 2013-02-09T19:34:14.550 に答える
0
あなたがそれに関してこれ以上の情報源を見つけるつもりかどうかはわかりません。k次元の線分がどのように機能するかを理解するのは人々に任されていると思います。あなたの立場で、私はそれでできる問題を解決しようとします。簡単な例（そして、このクエリはいくつかの前処理を使用してO（1）で実行できることを認識しています）：長方形の範囲の合計。つまり、数値で満たされた行列が与えられた場合、部分行列の合計を求めるクエリに答えます。ここでは、1つのsemgentツリーを使用して高さを分割し、各ノードで幅ベースの合計の追加のセグメントツリーを作成できます。それができれば、2-dimについて知っておくべきことがすべてわかっています。セグメントツリー。次の課題は、単一の要素を更新できるようにすることです。これは、「アート」を使用する必要があるため、より速く困難になります。変更を適切に伝播するため（セグメントツリー内のある種のキャッシュを考えてみてください）。:)
于 2013-02-09T19:21:05.170 に答える