如何实现累积产品表？

Question

鉴于以下问题:

有一个k整数序列,名为s,可以有2个操作,

1)Sum [i,j] - s [i] + s [i + 1] + ... + s [j]的值是多少？

2)更新[i,val] - 将s [i]的值更改为val.

我相信这里的大多数人都听说过使用累积频率表/ fenwick树来优化复杂性.

现在,如果我不想查询总和,而是我想执行以下操作:

乘积[i,j] - s [i]*s [i + 1]*...*s [j]的值是多少？

新问题起初似乎微不足道,至少对于第一次操作Product [i,j].

假设我使用名为f的累积产品表:

1. 在首先想到的,当我们调用更新[我,VAL] ,我们应该划分累积性的产品F [Z]为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个操作的累积产品表？

Answer 1

维护2张表：

• 累积产品表，其中所有零条目都已存储为 1（以避免影响其他条目）。
• 存储零条目数量的累积和。如果 f[i] 为 0，则每个条目 s[i] 为 1；如果非零，则每个条目 s[i] 为 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

row 是索引，f 是因子，cum_f 是 f 将零视为 1 的累积乘积，isZero 是指示 f 是否为零的标志，cum_isZero 是 isZero 标志的累积和，log(f)是 f 以 10 为底的对数，cum_log(f) 是 log_f 的累积和，将 -inf 视为零。

要计算从第 i 行到第 j 行（含）的范围的总和或乘积，请从第 [j] 行中减去第 [i-1] 行，并使用第 -1 行作为“虚拟”行。

要计算第 0-2 行中 f 的累积乘积，首先求 isZero 的累积和： cum_isZero[2] - cum_isZero[-1] = 1 - 0 = 1。该值非零，因此累积乘积为 0

要计算第 2-4 行中 f 的累积乘积，请执行上述操作： cum_isZero[4] - cum_isZero[1] = 0 - 0 = 0。这是零，因此我们可以计算乘积。

使用 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