文章目录

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，用树状数组操作。

就可以理解为前缀和与差分