前缀和 & 差分

1. 前缀和

前缀和是一种支持不带修改，多次查询的数据结构。

1.1 一维前缀和

维护前缀和数组 \(b_i=\sum\limits_{j=1}^i a_i\)，则 \(b\) 数组还可以通过递推式 \(b_i=b_{i-1}+a_i\) 得到。

当需要求区间 \([l,r]\) 的和，就可以通过 \(b\) 数组 \(b_r-b_{l-1}\) 得到，时间复杂度 \(\mathcal{O}(1)\)。

1.2 二维前缀和

类比一维前缀和，令前缀和数组 \(b_{i,j}=\sum\limits_{k=1}^i \sum\limits_{l=1}^j a_{k,l}\)。

观察上图可知，\(b_{i,j}=S_1+S_2+S_3+a_{i,j}\)，而 \(b_{i,j-1}=S_1+S_3\)，\(b_{i-1,j}=S_1+S_2\)，\(b_{i-1,j-1}=S_1\)，由容斥原理可以得到 \(b_{i,j}=b_{i-1,j}+b_{j,i-1}-b_{i-1,j-1}+a_{i,j}\)。

当需要查询 \((x1,y1)\sim(x2,y2)\) 子矩阵的和时，类比上述过程，易得 \(sum=b_{x2,y2}-b_{x2,y1-1}-b_{x1-1,y2}+b_{x1-1,y1-1}\)。

所以当我们处理出 \(b\) 数组之后，之后即可 \(\mathcal{O}(1)\) 查询了。