整数配列内のサブ配列の合計を求める

Question

N個の正の整数の配列が与えられているとします。それは、n*(n+1)/2サブアレイを含むことができ、単一要素サブアレイを含む。各サブアレイの合計はSです。サブ配列の数がO(n^2)であることから、すべてのサブ配列に対してS'sを見つけることは明らかにO(n^2)です。多くの合計S'sも繰り返すことができます。 O(n logn)のすべての別個の合計（正確な合計値ではなく、カウントのみ）の数を見つける方法はありますか？

私はアプローチを試みましたが途中で固執しました。私はインデックス1からnに配列を繰り返しました。
と言いますと、a[i]は指定された配列です。各インデックスについて、i、a[i]は、a[i-1]が含まれるすべての合計に加算され、それ自体も個々の要素として含まれます。 a[i-1]が含まれている合計のうち、2つの合計の差がa[i]であれば、重複が出現します。つまり、合計SpとSqはa[i-1]になり、両方の違いはa[i]となります。次にSp + a[i]はSqに等しく、Sqを二重にする。

セイC[i]は、a[i]に終わる別個の合計のカウントです。
だからC[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i]です。

しかし問題は、ペア数の一部をO(log n)に見つけることです。私にこれについてのヒントを教えてください。もし私が間違っていて、まったく別のアプローチが必要なら、それを指摘してください。

Answer 1

Sが大きすぎない場合、1つの（高速の）多項式乗算を使って別々の合計を数えることができます。 Sが大きい場合、Nは2次アルゴリズムを使用するのに十分小さいと思われます。

x_1、x_2、...、x_nを配列要素とします。 y_0 = 0、y_i = x_1 + x_2 + ... + x_iとする。 P（z）= z^{y_0} + z^{y_1} + ... + z^{y_n}とする。多項式P（z）* P（z^{ - 1}）の積を計算します。 k> 0のz^kの係数は、kがサブアレイの和である場合に限り非ゼロです。したがって、正の係数の非ゼロ係数の数を読み取るだけで済みます。さらに、zの累乗は-SからSの範囲であるため、S logSのオーダで時間がかかります。

Answer 2

サブアレイを一種のツリーとして見ることができます。サブアレイ[0,3]は、[0,1]と[2,3]に分けることができます。

ノードがサブアレイの長さで定義され、元の配列内の開始オフセットが定義されているツリーを構築し、サブアレイを計算するたびにこのツリーに結果を格納します。

サブアレイを計算するときに、このツリーに既存の事前計算値があるかどうかを確認できます。

また、分割する際に、異なるCPUコアで配列の一部を計算することもできます（問題がある場合）。

このソリューションでは、すべての値を特別な値ではなく一度に必要としないことを前提としています。 前者には、よりスマートな解決策があるかもしれません。

また、10000以上の要素の数についても言及しています。そうでなければ、そのような仕事は素晴らしい運動ですが、実用的価値はあまりありません。