为何Fenwick Tree(BIT)的区间更新不对区间外节点产生影响?
Fenwick Tree(BIT)区间更新逻辑疑惑
我们假设有这样一棵Fenwick Tree(BIT):
图中绿色代表节点值,红色代表节点覆盖的区间(包含两端),底部是构建该BIT的原始数组,此BIT用于计算区间[l, r]的元素和。
我已经理解了单点查询的方式:查询索引x时,通过位运算回溯父节点直到索引0,得到[1, x]的前缀和,再用query(r) - query(l-1)计算[l, r]的区间和。
单点更新操作我也能明白:给索引x的元素加值y,同时给所有包含x的区间对应的节点加y。比如更新x=5,y=7时,需依次更新节点6、8、16、32等,更新后节点5的值为8,节点6(覆盖[5,6])的值为10,节点8(覆盖[1,8])的值为53。
但我对区间更新操作完全搞不懂:资料里都说针对[l, r]区间加值y的操作,只需给索引l加y,再给索引r+1加-y。比如更新[5,6]区间时,这种操作看起来根本不会影响[1,8]节点,那查询索引8的前缀和时不就会得到错误结果吗?
我原本以为区间更新应该遍历[l, r]的每个索引,逐个执行完整的单点更新操作,但显然这个思路是错的。我完全搞不懂为什么要采用这种区间更新的方式,也不知道该怎么理解这种BIT的逻辑。
内容的提问来源于stack exchange,提问作者Szyszka947
相关产品推荐
相关产品推荐

