c++ - C++ のセグメント ツリーの STL

Question

セグメント ツリーの STL はありますか?

競技プログラミングでは、セグメント ツリーのコーディングに多くの時間がかかります。そのためのSTLがあれば、多くの時間を節約できるのではないかと思います。

Answer 1

「セグメントツリー」とは、実際にはレンジツリーを意味すると思います。これは、一連の間隔を格納するためのより特殊な構造よりも、プログラミングコンテストでより一般的に使用されています。

C++ 標準ライブラリにはそのようなコンテナーはありませんが、ACM コンテストに参加している場合は、独自のコンテナーを作成し、必要に応じて単純にコピーすることを検討できます。ここで私自身の実装(遅延伝播を含む) を見つけることができますが、Web を検索すると、おそらくより一般的なバージョンを見つけることができます。

最小値または最大値ではなく合計が必要なアプリケーションでは、セグメント ツリーの代わりにバイナリ インデックス ツリーを使用できます。これは、より高速で、メモリ使用量が少なく、コーディングも簡単です (約 12 行以下)。