1
サブアレイの問題：整数配列A（正の数のみ）を指定すると、長さSの合計が連続していますか？これにスライディングウィンドウの解はO（N）です。多くのサブアレイ集計クエリ
静的配列にこのようなクエリSがたくさんある場合、前処理を行うことができます。 O（N^2）のすべての部分配列和を計算し、それらをハッシュテーブルに格納することができます。これはまた、O（N^2）空間を占有する。次に、ハッシュテーブルからSを検索するだけで、O（1）のクエリを処理できます。
私の質問はO（N log N）前処理ですか？たとえそれがO（log N）にクエリを落としたとしても。
「これに対するスライディングウィンドウの解決策はO（N）」アプローチですか？問題を完全に指定しましたか？ – MBo
よく知られている基本的なサブアレイサム問題を完全に理解していますか？ –
サブアレイを選択するのはちょっと難しいようですが、O（N ** 2）に相当する2つのインデックスを選択する必要があります。 –