2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – ryan
    Commented May 15, 2017 at 23:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.