一、前缀和

1. 一维前缀和

原数组：$a_1,a_2,...,a_n$

前缀和：$s_i = a_1+a_2+..+a_i$

• 如何求$s_i$

  for循环遍历到i，累加

  注意边界值$s_0=0$，因此，不会有特判情况

• 前缀和作用

  能快速求出数组里一段区间的和$[l,r]=s_r-s_{l-1}$

2. 二维前缀和

原数组：$a_{ij}$

前缀和：$s_{ij}$表示点$i,j$左上角矩阵的和

• 如何求$s_i$

  递推公式

  $s_{i,j}=s_{i,j-1}+s_{i-1,j}-s_{i-1,j-1}+a_{i,j}$

  

• 前缀和作用

  能快速求出子矩阵的和

  

  蓝色区域的和=大区域-红色区域-绿色区域+紫色区域

  $s=s_{x2,y2}-s_{x2,y1-1}-s_{x1-1,y2}+s_{x1-1,y1-1}$

二、差分—前缀和的逆运算

1. 一维差分

<aside> 💡 原数组：$a_1,a_2,...,a_n$

构造差分数组：$b_1,b_2,...,b_n$

使得$a_i=b_1+b_2+...+b_i$

</aside>

差分的作用

• 快速求原数组：对差分数组求和即可求得原数组
  • $O(n):B -> A$
• 多个操作：数组某个区间全部数据加上某个值，操作完成后求原数组只需对差分数组求和
  • 如果$[l,r]$有m个元素，那么差分会使每次操作从$O(m)$变成$O(1)$
  • 如果在$[l,r]+c$
    • 如果$b_l+c$，则从$a_l,a_{l+1},...,a_n$都会加上$c$，因为这些值都会加到$b_l+c$
    • 而我们只需在$[l,r]$的元素加$c$，因此需要$b_{r+1}-c$
    • 因此，每次操作只需修改$b_l+c$和$b_{r+1}-c$

如何构造？