【模板】差分题解

题目大意

有一个长度为的序列，初始时所有元素均为。
进行次操作，每次操作给出三个整数，表示将区间内的每个元素都加上。
请你输出所有操作结束后的序列。

思路分析

如果直接模拟每次操作，对区间内的每个元素逐个加上，时间复杂度为，在数据范围较大时不可接受。

我们需要一种更高效的方法，差分就是解决区间加法的经典技巧。

差分数组

设原数组为（初始全为）。
定义差分数组，其中：

对于，

差分数组有一个重要性质：
如果对原数组的区间加上，那么对应的差分数组只需要进行两次单点修改：

（当时）

这是因为：

区间加后，比多增加了，所以增加。
比少增加了，所以减少。

算法流程

初始化差分数组长度为，全部为。
对于每次操作：
最后对差分数组做前缀和，还原出原数组：
输出。

代码实现

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> diff(n + 2, 0); // 差分数组，下标从1开始

    for (int i = 0; i < m; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        diff[l] += x;
        diff[r + 1] -= x;
    }

    // 还原原数组并输出
    long long cur = 0;
    for (int i = 1; i <= n; ++i) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }

    return 0;
}

Python 代码

def main():
    import sys
    input = sys.stdin.readline

    n, m = map(int, input().split())
    diff = [0] * (n + 2)  # 差分数组，下标从1开始

    for _ in range(m):
        l, r, x = map(int, input().split())
        diff[l] += x
        diff[r + 1] -= x

    cur = 0
    ans = []
    for i in range(1, n + 1):
        cur += diff[i]
        ans.append(str(cur))
    print(' '.join(ans))

if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：，因为每次操作只做两次单点修改，最后需要一次的前缀和还原。
空间复杂度：，用于存储差分数组。

注意事项

下标范围：操作区间是 -indexed，所以差分数组开到可以避免越界。
数据类型：序列元素可能变得很大（根据数据范围，最大约，操作次数也很大），建议使用 long long（C++）或 Python 的无限整数。
输出格式：最后输出一行，元素之间用空格隔开，末尾无多余空格。

扩展思考

如果要求在线查询某个位置的值，差分也能高效处理。
差分思想可以扩展到二维数组（二维差分），用于快速子矩阵加法和查询。

本题是差分算法的模板题，掌握差分可以高效解决区间加法问题。

【模板】差分 题解