6

Given the following problem:

There is a sequence of k integers, named s for which there can be 2 operations,

1) Sum[i,j] - What is the value of s[i]+s[i+1]+...+s[j]?

2) Update[i,val] - Change the value of s[i] to val.

I am sure most people here have heard of using a cumulative frequency table/fenwick tree to optimize the complexity.

Now, if I don't want to query the sum but instead I want to perform the following:

Product[i,j] - What is the value of s[i] * s[i+1] * ... * s[j]?

The new problem seems trivial at first, at least for the first operation Product[i,j].

Assuming I am using a cummulative product table named f:

  1. At first thought, when we call Update[i,val], we should divide the cummulative products at f[z] for z from i -> j by the old value of s[i] then multiply by the new value.

  2. But we will face 2 issues if the old value of s[i] is 0:

    • Division by 0. But this is easily tackled by checking if the old value of s[i] is 0.

    • The product of any real number with 0 is 0. This result will cause all other values from f[i] to f[j] to be 0. So we are unable to successfully perform Update[i,val]. This problem is not so trivial as it affects other values besides f[i].

Does anyone have any ideas how I could implement a cummulative product table that supports the 2 operations mentioned above?

4

1 回答 1

2

Maintain 2 tables:

  • A cumulative product table, in which all zero entries have been stored as ones instead (to avoid affecting other entries).
  • A cumulative sum storing the number of zero entries. Each entry s[i] is 1 if f[i] is 0 and 0 if non-zero.

To compute the cumulative product, first calculate the cumulative sum of zero entries in the given range. If non-zero (i.e. there is 1 or more zero in the range) then the cumulative product is zero. If zero then calculate the cumulative product as you describe.

It might be more accurate to store your factors as logarithms in some base and compute the cumulative product as a sum of log values. You'd just be computing 2 cumulative sums. In that case you would need to store zero entries in the product table as log values of 0 (i.e. values of 1).

Here's an example, using a simple cumulative sum (not Fenwick trees, but you could easily use them instead):

 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 is the index, f is the factor, cum_f is the cumulative product of f treating zeros as if they were ones, isZero is a flag to indicate if f is zero, cum_isZero is the cumulative sum of the isZero flags, log(f) is the log of f in base 10, cum_log(f) is the cumulative sum of log_f, treating -inf as zero.

To calculate the sum or product of a range from row i to row j (inclusive), subtract row[i-1] from row[j], using row -1 as a "virtual" row.

To calculate the cumulative product of f in rows 0-2, first find the cumulative sum of isZero: cum_isZero[2] - cum_isZero[-1] = 1 - 0 = 1. That's non-zero, so the cumulative product is 0

To calculate the cumulative product of f in rows 2-4, do as above: cum_isZero[4] - cum_isZero[1] = 0 - 0 = 0. That's zero, so we can calculate the product.

Using cum_f: cum_f[4] / cum_f[1] = 72 / 3 = 24 = 4 x 2 x 3

Using cum_log_f: cum_log(f)[4] - cum_log(f)[1] = 1.857 - 0.477 = 1.38

101.38 = approx 24

于 2016-08-20T03:02:15.290 回答