はじめに
今日は、配列の要素の合計を
l 番目から
r番目まで効果的に計算する方法についてお話したいと思います。 これらのメソッドの中で最も有名なものはセグメントツリー（RSQ）ですが、書くことと理解することはかなり難しいので、より単純ですが、あまり効果的ではない-Sqrt分解を提供したいと思います。
問題の正式な声明
配列A [0..n-1]が与えられた場合、配列の境界を超えない任意の
lと
rの要素A [l..r]の合計を効率的に計算する方法を学習する必要があります。 一般性を失うことなく、
l <= rと仮定します。
解決策
Sqrt分解法を使用します。 この方法により、次の問題を解決できます。
。 この方法の本質は、元の配列を長さのブロックに分割することです
事前計算を行います。 明らかに、そのようなブロックはうまくいきます
個。
nが完全に割り切れない場合、最後のブロックは他のブロックより短くなる可能性があります
でも心配することはありません。
ブロックの長さlen =
（ルート値は切り上げられると仮定します）。
また、
nが lenで完全に割り切れない場合、最後のブロックの長さは
lenではなく、それより短くなります。 前述のとおり、これは重要ではありません。
次に、配列Bを作成します。B[i]に、
i番目のブロックの要素の合計を格納します。 明らかに、そのような推定には時間がかかります
時間なので、配列Aを通過するだけです。
したがって、金額を要求するときに、配列のすべての要素を
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からその要素を再計算するだけです。 これは明らかに必要です
操作。 また、このメソッドを使用して、配列のセグメントの最小値と最大値を計算できます。 これを行うには、Bの対応するブロックの最小値と最大値を保存する必要があります。