How do I efficiently multiply a range of values of

问题:

The naive way would be to linearly iterate the range and multiply with each number in the range.

Example: Array: {1,2,3,4,5,6,7,8,9,10}; Multiply index 3 to index 8 with 2. Assuming one based index.

Result array should be : {1,2,6,8,10,12,14,16,9,10};

I know that Binary indexed tree can be used for the 'sum' part. How can I efficiently multiply a given range with a number?

回答1:

If you want to actually modify the array, you can't do better than the naive linear algorithm: you have to iterate the entire range and modify each index accordingly.

If you mean something like, you have update operations like you described and a query operation find the sum in the range from x to y, then a segment tree can help like so.

For each update operation left, right, value, for each node with an associated range included in [left, right], its sum gets multiplied by value, so update this accordingly and stop proceeding with the recursion. This will also apply to intervals you will not recurse on, so instead of actually updating the sum, store in each node how much its associated interval was multiplied by.

When returning from recursion, you can recompute the actual sums according to this info.

Pseudocode:

Update(node, left, right, value):
  if [left, right] does not intersect node.associated_range:
    return     

  if [left, right] included in node.associated_range:
    node.multiplications *= value # 1 initially
    return

  Update(node.left, left, right, value)
  Update(node.right, left, right, value)

  node.sum = node.left.sum * node.left.multiplications +
             node.right.sum * node.right.multiplications

Basically, each node will store its sum by only considering the multiplications in child segments. Its true sum will be lazily computed during a query by using the information regarding the multiplications that affected that interval.

A sum query is then performed almost like a usual query on a segment tree: just make sure to multiply the sums by how much them or parent intervals were multiplied by.

Pseudocode:

Query(node, multiplications = 1, left, right):
  if [left, right] does not intersect node.associated_range:
    return 0     

  if [left, right] included in node.associated_range:
    return node.sum * multiplications

  return Query(node.left, multiplications * node.multiplications, left, right) +
         Query(node.right, multiplications * node.multiplications, left, right)

The function that initially builds the tree is left as an exercise (you can do a bit better than calling update n times).

回答2:

By BIT you can also update a range.(Range update by BIT).

You can also use Segment Tree, RMQ. You can multiply with a given number easily.

Nice tutorial about ST and RMQ. RMQ Topcoder and Segment Tree

回答3:

As far as I know the only way is to iterate through the vector, and apply the multiplication.

You could define a function like so:

void VecMultiply(std::vector<int>& pVector, int Multiplier);

and implement it like:

void VecMultiply(std::vector<int>& pVector, int Multiplier)
{
    for (unsigned int i = 0; i < pVector.size(); i++)
    {
        *pVector[i] *= Multiplier;
    }
}

Or you could even pass a vector of anything multiplied by anything using templates:

template<typename T>
template<typename M>
void VecMultiply(std::vector<T>& pVector, M Multiplier)
    {
        for (unsigned int i = 0; i < pVector.size(); i++)
        {
            *pVector[i] *= Multiplier;
        }
    }

回答4:

You can follow a linear approach and code it in C++11 like

std::array<int, 10> nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::for_each(nums.begin() + 2, nums.begin() + 8, [](int & n) { n *= 2; });
for (int & n : nums) std::cout << n << " ";

Output

1 2 6 8 10 12 14 16 9 10