前缀和数组与差分数组

一维前缀和

对于一维数组nums，其前缀和数组prefix为 \[ prefix[i] = \sum\limits^{i}_{1} nums[i] \]

实际中多在前面加一个0，这样prefix[i]就刚好是nums数组的前i项和。

一维差分数组

一维数组nums的差分数组diff定义：

\[ diff[i] = nums[i] - nums[i - 1] \]

二维差分、二维前缀和与一维差分一维前缀和同理。

二维前缀和、二维差分定义以及例题详见Hard题学算法(二维前缀和+二维差分）

从差分数组、前缀和数组求原数组

差分数组求原数组：差分数组的前缀和数组就是原数组

前缀和数组求原数组（以二维为例,默认在前面添加了一维的0防止越界）：

\[nums[i][j] = prefix[i + 1][j + 1] - prefix[i][j + 1] - prefix[i + 1][j] + prefix[i][j]\]