-2

当我们进行范围更新时，有人可以帮助我理解二叉索引树吗？为什么不更新每个元素，为什么只更新开始元素和结束元素

例如 0

我们必须将 BIT 中的数组元素范围更新为 arr[x] 到 arr[y] 。根据二叉索引树点更新函数。它将更新索引 x 的累积频率，并且所有那些索引 > 比 x 都会受到更新的影响.

但是，如果我们使用点更新功能进行范围更新。那为什么我们不使用点更新功能更新每个大于 x 和小于 y 的索引。由于范围更新意味着每个元素都应该使用值进行更新，并且更新起始索引和一个高于结束索引如何涵盖所有更新

为什么我们不做

.....................................................

 for (i =[x] to [y])
    pointupdate(ar[i],val);// why we are not doing this 

update(p, v): //point update
  for (; p <= N; p += p&(-p))
    ft[p] += v   

# Add v to A[a...b] 
update(a, b, v):     // why we are using this only for update of one element how other elements greater than a will be coverd
  update(a, v)     
  update(b + 1, -v)

我

4

1 回答 1

0

当您更新 时BIT[a]+=v，这意味着对每个索引x>=a的查询都会看到v增量。

要以这种方式执行范围更新，您v需要在范围开始时递增，v在范围结束后递减。这意味着只有 和 之间a的b增量是可见的。

于 2016-07-17T00:59:19.987 回答