Как эффективно умножить диапазон значений массива на заданное число?

Наивным способом было бы линейно итерировать диапазон и умножать на каждое число в диапазоне.

Пример: массив: {1,2,3,4,5,6,7,8,9,10}; Умножьте индекс 3 на индекс 8 с 2. Предполагая один основанный индекс.

Массив результатов должен быть: {1,2,6,8,10,12,14,16,9,10};

Я знаю, что двоичное индексируемое дерево может использоваться для части 'sum'. Как я могу эффективно умножить заданный диапазон на число?

Источник

5 ответов

Если вы действительно хотите изменить массив, вы не можете добиться большего успеха, чем простой линейный алгоритм: вы должны выполнить итерацию всего диапазона и соответственно изменить каждый индекс.

Если вы имеете в виду что-то вроде, у вас есть операции обновления, как вы описали, и операция запроса find the sum in the range from x to yтогда дерево сегментов может помочь вот так.

Для каждой операции обновления left, right, valueдля каждого узла с соответствующим диапазоном, включенным в [left, right], его сумма умножается на valueпоэтому обновите это соответствующим образом и прекратите выполнение рекурсии. Это также будет применяться к интервалам, на которые вы не будете рассчитывать, поэтому вместо фактического обновления суммы сохраняйте в каждом узле, на сколько умножился связанный с ним интервал.

Возвращаясь из рекурсии, вы можете пересчитать фактические суммы в соответствии с этой информацией.

Псевдокод:

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

По сути, каждый узел будет хранить свою сумму, рассматривая только умножения в дочерних сегментах. Его истинная сумма будет лениво вычисляться во время запроса с использованием информации, касающейся умножений, повлиявших на этот интервал.

Запрос суммы затем выполняется почти как обычный запрос в дереве сегментов: просто убедитесь, что суммы умножены на то, на сколько они или родительские интервалы были умножены.

Псевдокод:

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)

Функция, которая изначально строит дерево, остается в качестве упражнения (вы можете сделать немного лучше, чем вызывать update n раз).

Источник

Вы можете следовать линейному подходу и кодировать его в C++11 лайк

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 << " ";

Выход

1 2 6 8 10 12 14 16 9 10
Источник

По BIT вы также можете обновить диапазон.( Обновление диапазона по BIT).

Вы также можете использовать дерево сегментов, RMQ. Вы можете умножить с данным числом легко.

Хороший учебник о ST и RMQ. RMQ Topcoder и сегментное дерево

Источник

Насколько я знаю, единственный способ - это перебрать вектор и применить умножение.

Вы можете определить функцию следующим образом:

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

и реализовать это как:

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

Или вы можете даже передать вектор чего-либо, умноженного на что-либо, используя шаблоны:

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;
        }
    }
Источник

может быть также в векторной форме:

      std::vector<int> nums={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };;
int c=2;
std::transform(nums.begin()+2,nums.end(), nums.begin(), [&c](auto& n){return c*n;});
for (int & n : nums) std::cout << n << " ";
Источник
Другие вопросы по тегам