【小技巧】前缀和

一维前缀和

其实可以理解为数列前n项的和,定义一个数组a的前缀和s为:

s[i] = \sum_{j = 0}^{i}a[j]

二维前缀和

与一维前缀和类似:

s[i][j] = \sum_{n = 0}^{i}\sum_{m = 0}^{j}a[n][m]

用途

一般用于求区间和

在一维前缀和中,给定数组A[],要求回答m次询问,每次询问下标从i到j的和。

于是我们就可以O(n)预处理前缀和s[],然后对于每次询问,以O(1)回答s[j] – s[i],便是答案。

在二维前缀和中,和一维类似。

回答ans = s[i2][j2] – s[i2][j1 – 1] – s[i1 – 1][j2] +s[i1 – 1][j1 – 1]

这里也称差分序列