multiplicationfenwick-tree

multiplication using fenwick tree

We can do updation in a fenwick tree like adding a value and multiplication by a value. I have the following code for adding a value x to the element at position l .

while(l <= n-1)
{
    tree[l] = tree[l] + x;
    l = l + (l&(-l));
}

Similarly I want to perform the multiplication operation.I am not getting how to do it. Any help is appreciable.

Solution

  • Compute the difference between the old and new node values, then use the addition logic to add that difference to the node value.