二叉索引树(范围更新和点查询)

Question

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

例如 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)     

我

Answer 1

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

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