前缀和与差分算法c++

前缀和（Prefix Sum）和差分算法是计算机科学中用于处理数组数据的一种高效技巧，通常用于解决区间查询、求和等问题。在C++中，它们常用于动态规划或者需要快速计算某个区间内元素和的情况。

**前缀和（Cumulative Sum）**：
前缀和数组是一个元素序列，其中每个元素都是前一个元素加上当前元素的结果。例如，给定数组arr = [1, 2, 3, 4]，其前缀和数组psum会是[1, 3, 6, 10]。前缀和可以用来快速计算任意位置之前所有元素的和。

int prefixSum(vector<int>& arr) {
    for (size_t i = 1; i < arr.size(); ++i) {
        arr[i] += arr[i - 1];
    }
    return arr;
}

**差分数组（Difference Array）**：
差分数组则是前缀和数组的逐项相减结果。它记录了原数组相邻元素之间的差异。对于上面的例子，差分数组diff会是[2, 3, 4]，表示从第一个元素到第二个元素增加了2，以此类推。

vector<int> diffArray(const vector<int>& psum) {
    vector<int> diff(psum.size() - 1);
    for (size_t i = 1; i < psum.size(); ++i) {
        diff[i - 1] = psum[i] - psum[i - 1];
    }
    return diff;
}

这两个技术常用于优化空间复杂度和减少查询时间。比如在统计连续子数组的最大和问题中，可以用到前缀和；而在计算两个子数组之和的问题上，可以先计算前缀和再通过差分找到所需的区间和。