[数据结构与算法]高级数据结构(1)

前缀和

• 对于一个序列$a$，它的“前缀和”序列$s$可以通过递推计算
  $$s[i]=\sum _{j=1}^{i}a[j]=s[i?1]+a[i]$$

• 区间和，即序列$a$在$[l,r]$之间的数之和，可以通过“前缀和”相减求得
  $$\sum _{i=l}^{r}a[i]=s[r]?s[l?1]$$

二维前缀和

• 在二维数组中，二维前缀和如下：
  $$\begin{gathered} s[i,j]=\sum _{x=1}^i\sum _{y=1}^{i}a[i,j] \\ =s[i?1,j]+s[i,j?1]?s[i?1,j?1]+a[i,j] \end{gathered}$$
• 区间和，以边长为$r$的的正方形为例：
  $$\begin{gathered} \sum _{x=i?r+1}^i\sum _{y=j?r+1}^{i}a[x,y] \\ =s[i,j]?s[i?r,j]?s[i,j?r]+s[i?r,j?r] \end{gathered}$$
• $O(N^2)$递推求出二维前缀和，$O(N^2)$枚举边长为$r$的正方形的右下角坐标$(i,j)$，即可$O(1)$计算正方形内数字之和

差分

• 对于一个序列$a$，定义基于$a$的差分序列$b$：
  $$\begin{gathered} b[1]=a[1] \\ b[i]=a[i]?a[i?1](2\le i\le n) \end{gathered}$$
• 前缀和与差分是互逆运算，差分序列的前缀和序列即为原序列$a$，而前缀和序列的差分序列也是原序列$a$
• 把序列$a$的区间$[l,r]$加上$d$（区间修改），只要将其差分序列$b_l+d$, $b_{r+1}?d$，其它元素不变，即将“区间修改”，变为“单点修改”