6

次の問題があるとします。

sという名前の k 個の整数のシーケンスがあり、2 つの操作が可能です。

1) Sum[i,j] - s[i]+s[i+1]+...+s[j] の値は?

2) Update[i,val] - s[i] の値をvalに変更します。

ここにいるほとんどの人は、累積度数表/フェンウィック ツリーを使用して複雑さを最適化することについて聞いたことがあると思います。

ここで、合計をクエリしたくないが、代わりに次のことを実行したい場合:

Product[i,j] - s[i] * s[i+1] * ... * s[j] の値は?

新しい問題は、少なくとも最初の操作Product[i,j]については、最初は些細なことのように見えます。

fという名前の累積製品テーブルを使用していると仮定します。

  1. 最初に考えたのは、 Update[i,val]を呼び出すとき、 i -> j からの z のf[z]での累積積をs[i] の古い値で割り、新しい値で乗算する必要があるということです。

  2. しかし、 s[i] の古い値が 0の場合、2 つの問題に直面します。

    • 0 による除算。ただし、これは s[i] の古い値が 0 であるかどうかを確認することで簡単に対処できます。

    • 実数と 0 の積は 0 です。この結果により、f[i]からf[j]までの他のすべての値が 0 になります。したがって、 Update[i,val]を正常に実行できません。この問題は、 f[i]以外の値に影響するため、それほど単純ではありません。

上記の2つの操作をサポートする累積製品テーブルをどのように実装できるか考えている人はいますか?

4

1 に答える 1

2

2 つのテーブルを維持します。

  • 代わりにすべてのゼロ エントリが 1 として格納されている累積製品テーブル (他のエントリへの影響を避けるため)。
  • ゼロ エントリの数を格納する累積合計。各エントリ s[i] は、f[i] が 0 の場合は 1 であり、ゼロ以外の場合は 0 です。

累積積を計算するには、まず、指定された範囲内のゼロ エントリの累積合計を計算します。ゼロでない場合 (つまり、範囲内に 1 つ以上のゼロがある場合)、累積積はゼロです。ゼロの場合は、説明したように累積積を計算します。

因数を底の対数として保存し、累積積を対数値の合計として計算する方が正確な場合があります。2 つの累積合計を計算するだけです。その場合、0 のログ値 (つまり、1 の値) として製品テーブルにゼロ エントリを格納する必要があります。

単純な累積合計を使用した例を次に示します (フェンウィック ツリーではありませんが、代わりに簡単に使用できます)。

 row   f   cum_f   isZero  cum_isZero  log(f)  cum_log(f)

-1     1     1       0         0        0         0

 0     3     3       0         0        0.477     0.477
 1     0     3       1         1        -inf      0.477
 2     4    12       0         1        0.602     1.079
 3     2    24       0         1        0.301     1.38
 4     3    72       0         1        0.477     1.857

行はインデックス、f は係数、cum_f はゼロを 1 として扱う f の累積積、isZero は f がゼロかどうかを示すフラグ、cum_isZero は isZero フラグの累積合計、log(f)は基数 10 の f の対数、cum_log(f) は -inf をゼロとして扱う log_f の累積和です。

行 i から行 j まで (両端を含む) の範囲の合計または積を計算するには、行 -1 を「仮想」行として使用して、行 [j] から行 [i-1] を減算します。

行 0 ～ 2 の f の累積積を計算するには、最初に isZero の累積和を見つけます: cum_isZero[2] - cum_isZero[-1] = 1 - 0 = 1. これはゼロではないため、累積積は 0 です。

行 2 ～ 4 の f の累積積を計算するには、上記のように実行します。

cum_f の使用: cum_f[4] / cum_f[1] = 72 / 3 = 24 = 4 x 2 x 3

cum_log_f の使用: cum_log(f)[4] - cum_log(f)[1] = 1.857 - 0.477 = 1.38

10 1.38 = 約 24

于 2016-08-20T03:02:15.290 に答える