如何实现累积乘积table？

Question

鉴于以下问题：

有一个由 k 个整数组成的序列，名为 s，它可以有 2 个操作，

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

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

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

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

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

新问题乍一看似乎微不足道，至少对于第一个操作 Product[i,j].

假设我正在使用名为 f:

的累积产品 table

一开始想到，当我们调用Update[i,val]时，我们应该在f[z]处划分累积乘积for z from i -> j 乘以 s[i] 的旧值，然后乘以新值。
但是如果s[i]的旧值为0，我们将面临2个问题：
- 除以 0。但这很容易通过检查 s[i] 的旧值是否为 0 来解决。
- 任何实数与0的乘积都是0。这个结果将导致从f[i]到f的所有其他值[j] 为 0。所以我们无法成功执行 Update[i,val]。这个问题不是那么微不足道，因为它会影响 f[i].

有谁知道如何实现支持上述 2 种操作的累积产品 table？

Answer 1

维护 2 tables:

累积乘积table，其中所有零条目都存储为一（以避免影响其他条目）。
存储零条目数的累积和。如果 f[i] 为 0，则每个条目 s[i] 为 1，如果非零，则为 0。

要计算累积乘积，首先计算给定范围内零项的累积和。如果非零（即范围内有 1 个或多个零），则累积乘积为零。如果为零，则按照您的描述计算累积乘积。

将因子存储为某些底数的对数并将累积乘积计算为对数值的总和可能更准确。您只需计算 2 个累计和。在这种情况下，您需要在产品 table 中将零个条目存储为 0 的对数值（即值 1）。

这是一个示例，使用简单的累积和（不是 Fenwick 树，但您可以轻松地使用它们）：

 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 将 0 视为 1 的累积乘积，isZero 是指示 f 是否为零的标志，cum_isZero是 isZero 标志的累加和，log(f) 是 f 以 10 为底的对数，cum_log(f) 是 log_f 的累加和，将 -inf 视为零。

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

计算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

如何实现累积乘积table？

How to implement a cumulative product table?

algorithm

cumulative-frequency