c++ - 如何有效地将数组的一系列值与给定数字相乘？

Question

最简单的方法是线性迭代范围并与范围中的每个数字相乘。

示例:数组:{1,2,3,4,5,6,7,8,9,10}； 将索引 3 到索引 8 乘以 2。假设基于一个索引。

结果数组应为:{1,2,6,8,10,12,14,16,9,10}；

我知道二叉索引树可用于“求和”部分。如何有效地将给定范围与数字相乘？

Answer 1

如果你想实际修改数组，你不能比朴素的线性算法做得更好:你必须迭代整个范围并相应地修改每个索引。

如果您的意思是，您有您所描述的更新操作和查询操作查找从 x 到 y 范围内的总和，那么线段树可以像这样提供帮助。

对于每个更新操作左、右、值，对于[左、右]中包含关联范围的每个节点，其总和乘以 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 次做得更好一点)。