【思想】前缀和、差分、倍增

前缀和、差分和倍增，没啥关系，只是单列太简短了…

前缀和

$sum[i]=a[i]+sum[i-1]$

$\sum_{i=l}^{r}a[i]=sum[r]-sum[l-1]$

差分

$d[i]=a[i]-a[i-1]$

区间修改$[x,y]$ ，那么$[x,y]$ 之间的数相对关系不变，差分数组的值不变，唯一变的是差分数组第$x$ 项（表示$x$ 与$x-1$ 的差，改变了）和第$y+1$ 项：以区间$[x,y]$ 加$c$ 为例，差分数组的修改为：$d[x]+=c,d[y+1]-=c$

$a[x]=\sum_{i=1}^{x}d[i]+a[0]$

另一种利用差分数组获得第$x$ 项的值的方法：差分数组$d$ 初始化为$0$ ，区间修改对$d$ 进行，而新的第$x$项值为：$a[x]+\sum_{i=1}^{x}d[i]$

倍增

• 原理：$1,2,4,8,...2^i$ 能表示$[1,2^{i+1})$ 中的所有数
• 核心：$a[x][i]=a[a[x][i-1]][i-1]$
• 将规模从$O(n)$ 降到$O(\log n)$ ，查询时遍历二进制每一位累和答案即可。