問題: ソートされた整数 a[N] の配列が与えられた場合、次のような種類のクエリを処理する必要があります
- [LR] p :すべての i=L...R についてa i C pの合計を求める
制約:
N< 10 5
1<=a i <=10 6
このようなクエリが Q 個あるとします。この問題を解決するためのより良い方法を提案してください。注意すべき点は次のとおりです
。すべてのクエリは事前に与えられます。つまり、オフライン アルゴリズムが機能します。
また、配列がソートされていることにも注意してください。
配列内の各要素は、小さい数で区切られています。アレイへの更新はありません。
ありがとう
PS: ブルート フォース アプローチは、複雑さを与える要素ごとに各クエリ要素を処理します: O(Q * N * (n のコストは r) を選択します) 。