一维：前缀和使用场景

求多个 l~r的和的值。

公式

预处理s[1~n]:

s[i] = s[i - 1] + a[i];

求 l~r的和
s[l~r] = s[r] - s[l - 1];

二维前缀和应用场景：

求多个矩形的和的值

s[i][j]  为从(1 , 1) -> (i , j)的矩形的和.

公式

预处理：

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];


求从(x1 , y1) -> (x2 , y2)的矩形的和:

temp = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];