前缀和 ​

一维前缀和 ​

前缀和也是可以用在异或运算上的。

原数组下标从 $0$ 开始：

• 定义：$s[i]=a[0]+a[1]+...+a[i-1]=\sum _{j=0}^{i-1}a[j]$ 。
• 构造：$s[0]=0$，$s[i]=s[i-1]+a[i-1]$ 。
• 使用：$sum(a[l\dots r])=s[r+1]-S[l]$ 。

原数组下标从 $1$ 开始：

• 定义：$s[i]=a[1]+a[2]+...+a[i]=\sum _{j=1}^{i}a[j]$ 。
• 构造：$s[0]=0$ ，$s[i]=s[i-1]+a[i]$ 。
• 使用：$sum(a[l\dots r])=S[r]-S[l-1]$ 。

二维前缀和 ​

矩阵横纵坐标均从 $1$ 开始：

• 定义：$s[i][j]=\mathrm{第}i\mathrm{行}j\mathrm{列}\mathrm{格}\mathrm{子}\mathrm{左}\mathrm{上}\mathrm{部}\mathrm{分}\mathrm{所}\mathrm{有}\mathrm{元}\mathrm{素}\mathrm{的}\mathrm{和}=\sum _{x=1}^i(\sum _{y=1}^{j}a[x][y])$ 。
• 构造：$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$ 。
• 使用：以 $(x1,y1)$ 为左上角，$(x2,y2)$ 为右下角的子矩阵的和为： $s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]$ 。