Наивным способом было бы линейное перебор диапазона и умножение на каждое число в диапазоне.
Пример: Массив: {1,2,3,4,5,6,7,8,9,10}; Умножьте индекс 3 на индекс 8 с 2. Предположим, что один базовый индекс.
Массив результатов должен быть: {1,2,6,8,10,12,14,16,9,10};
Я знаю, что двоичное индексированное дерево можно использовать для части «сумма». Как я могу эффективно умножить заданный диапазон на число?
Если вы действительно хотите изменить массив, вы не сможете добиться большего успеха, чем наивный линейный алгоритм: вам нужно перебрать весь диапазон и соответствующим образом изменить каждый индекс.
Если вы имеете в виду что-то вроде, у вас есть операции обновления, как вы описали, и операция запроса 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 раз).
С помощью 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;
}
}
Вы можете следовать линейному подходу и закодировать его в 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
