python前缀和差分

Python中的前缀和和差分是两种常用的算法技巧，用于解决一些与数组或序列相关的问题。

1. 前缀和（Prefix Sum）：
前缀和是指将数组中的元素依次相加得到的新数组。通过计算前缀和，可以在O(1)的时间复杂度内得到任意区间的和。具体步骤如下：
- 初始化一个长度为n+1的前缀和数组prefix_sum，其中prefix_sum = 0。
- 遍历原始数组nums，计算每个位置i的前缀和prefix_sum[i+1] = prefix_sum[i] + nums[i]。
- 最终得到的prefix_sum数组即为原始数组的前缀和数组。

2. 差分（Difference）：
差分是指通过计算相邻元素之间的差值得到的新数组。差分可以用于高效地更新原始数组的某个区间内的元素。具体步骤如下：
- 初始化一个长度为n的差分数组diff，其中diff[i] = nums[i] - nums[i-1]。
- 对于需要更新原始数组nums中某个区间[l, r]内的元素，只需将diff[l]增加val，diff[r+1]减去val。
- 最后根据差分数组diff可以通过累加得到更新后的原始数组。