文章目录
1 概述2 单点查询3 区间修改4 例题1 概述
首先引入差分数组d,设原数组为a,令d[i]=a[i]-a[i-1].由此关系式得
也就是a[j]等于d[j]的前 j 项和,即前缀和。
于此,我们的树状数组维护的是 d 的前缀和。
2 单点查询
有以上推理得,查询a[i]相当于查询d[i]的前缀和,用树状数组操作即可。(注意:树状数组维护的是d数组,不是原数组!)
3 区间修改
因为对a的区间[i,j]加x,就相当于a[i]比a[i-1]大x,a[j+1]比a[j]小x,就相当于对a[i]加x,对a[j+1]减x。
因为a[i]等于d[i]的前缀和,所以a[i]+x就相当于对d[i]的前缀和加x,可以用树状数组操作。
同理,a[j+1]-x等于b[j+1]的前缀和减x,用树状数组操作。
就可以理解为前缀和与差分