静的配列 a の区間 l...r の合計を O(n) 未満の漸近線で素早く計算する方法に関する問題があります。
配列 a を同じサイズの k 個のブロックに分割し、最初にそれぞれの要素の合計を計算しましょう。
リクエストに応答するとき、配列 a の要素を調べて結果に追加できます。また、ブロックの 1 つがセグメント内にある場合は、その合計を結果に追加して、結果をスキップできます。このブロックの要素。
このアルゴリズムでのクエリあたりの最大操作数は n / k + k であるため、最適な k は n の平方根に等しくなります。