差分数组

算法内容

本文件演示差分数组的基本思想。差分数组适合处理“区间统一增减、最后还原数组”的场景。

diffOf 将原数组转换为差分数组，其中 diff[i] = data[i] - data[i - 1]；dataOf 对差分数组求前缀和，还原原数组。主循环读取 l, r, diff，表示对半开区间 [l, r) 加上 diff，只需要执行 data_diff[l] += diff 和 data_diff[r] -= diff，再还原即可看到更新后的数组。区间更新为 O(1)，还原数组为 O(n)。

算法实现

#include <vector>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

void printVec(const vector<int> &v, const string& head = "")
{
    if(head != "") {
        cout << head << ": ";
    }
    for (int i : v)
    {
        cout << i << " ";
    }
    cout << "\n";
}

vector<int> diffOf(const vector<int> &v)
{
    int len = v.size();
    vector<int> diff(len, 0);
    diff[0] = v[0];
    for (int i = 1; i < len; i++)
    {
        diff[i] = v[i] - v[i - 1];
    }
    return diff;
}

vector<int> dataOf(const vector<int> &v)
{
    int len = v.size();
    vector<int> data(len, 0);
    data[0] = v[0];
    for (int i = 1; i < len; i++)
    {
        data[i] = v[i] + data[i - 1];
    }
    return data;
}

int main()
{
    vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8};
    vector<int> data_diff = diffOf(data);
    printVec(dataOf(data_diff), "data");
    printVec(data_diff, "diff");
    int l, r, diff; //区间 [l, r) 的所有数增加 diff
    while (cin >> l >> r >> diff)
    {
        data_diff[l] += diff;
        data_diff[r] -= diff;
        printVec(dataOf(data_diff), "data");
        printVec(data_diff, "diff");
    }
    return 0;
}