はじめに
今日は、配列の要素の合計をl 番目からr番目まで効果的に計算する方法についてお話したいと思います。 これらのメソッドの中で最も有名なものはセグメントツリー(RSQ)ですが、書くことと理解することはかなり難しいので、より単純ですが、あまり効果的ではない-Sqrt分解を提供したいと思います。
問題の正式な声明
配列A [0..n-1]が与えられた場合、配列の境界を超えない任意のlとrの要素A [l..r]の合計を効率的に計算する方法を学習する必要があります。 一般性を失うことなく、 l <= rと仮定します。
解決策
Sqrt分解法を使用します。 この方法により、次の問題を解決できます。




ブロックの長さlen =


また、 nが lenで完全に割り切れない場合、最後のブロックの長さはlenではなく、それより短くなります。 前述のとおり、これは重要ではありません。
次に、配列Bを作成します。B[i]に、 i番目のブロックの要素の合計を格納します。 明らかに、そのような推定には時間がかかります

したがって、金額を要求するときに、配列のすべての要素をlからrまで実行する必要はありません。すでに部分的な合計が計算されているからです。 例を考えてみましょう。
A = { 3、4、8、7、1、6、1、6 }、 len = 3、B [0] = 15、B [1] = 14、B [2] = 7とする。
そして、彼らは私たちに1番目から6番目までの要素の合計を尋ねます(最初から数えます)。

まず、配列の2つの要素を正直に調べ、4と8を追加する必要があります。これは、B [0]ではなく、一部だけが必要だからです。 次に、B [1]は既にカウントされており、14に等しいので、最後のブロックの全量を必要としないので、最後まで1を追加するため、配列を実行する必要はありません。
実装:
//配列A(指定)があり、Bは部分和の配列です。
// len-ブロック長
for(int i = 0; i <n; i ++)
B [i / len] + = A [i]; //ブロックの合計を計算します
// lとrは境界です
int i = l、sum = 0;
while(i <= r)
{
if(i%len == 0 && i + len -1 <= r)
{
sum + = B [i / len];
i + = len;
}
他に
{
sum + = A [i];
i ++;
}
}
合計が結果になります。
この方法のもう1つの利点は、配列の要素を非常に簡単に変更できることです。 配列Aの要素を変更するときは、変数要素が存在するBからその要素を再計算するだけです。 これは明らかに必要です
