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?