How to implement an aggregate product table?

Question

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'm sure most people here have heard of using the cumulative fenwick frequency table / tree to optimize complexity.

Now, if I do not want to request the amount, but instead I want to do the following:

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

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

Assuming I'm using a cummulative product table named f:

• First, when we call Update [i, val], we must divide the cumulative products by f [z] for z from i → j by the old value s [i], and then multiply by the new value.

• But we will encounter 2 problems if the old value of s [i] is 0:

  • Division by 0. But this is easy to solve by checking if the old value of s [i] is 0.

  • The product of any real number with 0 is 0. This result will result in all other values ​​from f [i] to f [j] being 0. Thus, we cannot successfully execute Update [i, val]. This problem is not so trivial as it affects values ​​other than f [i].

Does anyone have any ideas how I can implement an aggregate products table that supports the 2 operations mentioned above?

Answer 1

Maintain 2 tables:

• A cumulative product table in which all null entries were saved in their place (so as not to affect other entries).
• Cumulative amount that stores the number of zero records. Each entry s [i] is 1 if f [i] is 0 and 0 if it is nonzero.

To calculate the total product, first calculate the total amount of zero records in the given range. If non-zero (i.e., in the range of 1 or greater than zero), then the total product is zero. If zero then calculate the total product as you describe.

Perhaps it will be more accurate to store your factors as logarithms in some database and calculate the total product as the sum of the log values. You simply calculate 2 cumulative amounts. In this case, you will need to store the null entries in the product table as log values ​​of 0 (i.e., values ​​of 1).

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

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 

the string is the index, f is the coefficient, cum_f is the cumulative product of f, processing zeros as if they were ones, isZero is a flag indicating whether f is zero, cum_isZero is the sum of the isZero flags, log (f) is the logarithm of f in base 10, cum_log (f) is the total sum of log_f, processing as zero.

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

To calculate the cumulative product f in lines 0-2, first find the cumulative sum isZero: cum_isZero [2] - cum_isZero [-1] = 1 - 0 = 1. This is nonzero, therefore the cumulative product 0

To calculate the cumulative product f in lines 2-4, do this: cum_isZero [4] - cum_isZero [1] = 0 - 0 = 0. This is 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

10 ^1.38 = approximately 24