# Counter tree Fenwick for multiplication

I need to compute prefix product of an array. For this reason I want to use counter tree fenwick . Hehe is what I have for the usual Fenwick tree:

An array $T$ indexded from $0$ to $n$. $T[i]$ stores the product of $[F(i)..i]$ segment, where $F(i) = i\ \ \& \ \ (i+1)$.

For the counter tree I need another array $T'$, $T'[i]$ stores the product of $[(i+1)..F'(i)]$, where $F'(i) = i\ \ | \ \ (i + 1)$. Basically, the length of $[(i+1)..F'(i)]$ is equal to the length of $[F(i)..i]$

When I need to multiply an element of an array in a usual Fenwick tree by a certain value I just have to do the following procedure

multiply(index, value)
for (i = index; i < n; i = i | (i + 1))
T[i] = T[i] * value


And I do not really understand how to update $T'$. Could you help me please?

• Could you elaborate on what a 'Counter Tree' is in this context? I would think a normal Fenwick Tree would be fine for the prefix product of an array. The root contains the whole product, then when traversing simply divide away the sections of the tree which should not be included. This resource also might help. – ryan May 15 '17 at 23:13