tjkendev/segment-tree-beats

implementation of "segment tree beats"

"Segment Tree Beats" の実装

• Segment Tree Beatsの実装です
  • 試行錯誤して実装しています
• ランダムに生成するクエリによって、クエリ処理が正しく行われることを保証しようとしてます
  • 特定のケースに対して落ちる可能性は存在します

ファイルの説明

• basic: SGT Beatsの基本的な実装
• advanced: 応用問題の実装
• hi-normal: Historic Information を従来のセグ木で処理する実装
• hi-sgt-beats: Historic Information をSegment Tree Beatsで処理する実装

書いたブログ

• Segment Tree Beatsの実装メモ (基本まわり)
• Segment Tree Beatsの実装メモ (応用的な例題まわり)
• Segment Tree Beatsの実装メモ (Historic Informationまわり)

参考

• A simple introduction to "Segment tree beats"
• Segment Tree Beats - An introduction
• 区间最值操作与历史最值问题
• Segment Tree Beats!