セグメント ツリーを使用して、Joseph Flavius 問題を解決したいと考えています。単純なシミュレーション (つまり、並べられたリスト) はO(n^2). 私が達成したいのは、セグメントツリーから取得した特定の距離の配列にジャンプすることです。つまり、セグメントツリーは削除された要素の数に関する情報を保持し、ツリーから情報を取得すると、O(1) で削除する次の要素を見つけることができます。問題は、Joseph Flavius 問題で機能するようにセグメント ツリーに情報を保存する方法がわからないことです。
各ノードに保持される何らかの追加の値はありますか? しかし、次の要素に関するクエリを作成するにはどうすればよいでしょうか?