的幼稚的方法是将线性迭代的范围内，乘以在所述范围内的每个数。

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

例：数组：{1,2,3,4,5,6,7,8,9,10}; 指数乘以3到指数8 2.假设一家立足指数。

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

结果数组应该是：{1,2,6,8,10,12,14,16,9,10};

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?

推荐答案

如果你想真正修改数组，你不能这样做比天真的线性算法更好的：你必须遍历整个范围并相应修改各项指标

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.

如果你的意思是这样，你有更新的操作，如您所描述和查询操作查找范围内的总和，从X到Y ，然后段树可以帮助像这样。

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.

伪code

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.

伪code

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)

这是最初建立的树作为一个练习的功能（你可以做的比要求更新更好一点 N 次）。

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