学习笔记N-032

差分

更新: 2026-05-13
内容块: 22
阅读: 约 2 分钟
路径: 学习笔记 / C++ / C++算法

推论 1.差分是前缀和的逆运算，一个数组经过一次前缀和运算后再经过一次差分运算，得到原数组，反之亦然

推论 2.在原数组 i，j 的范围内都加 x，就等于在原数组的差分数组中的 i 位加 x，在 j+1 位减 x.显著降低同时修改数组中一串连续元素的复杂度.(从改变一串数O(n*m)变为了一次差分,一次修改两个数O(n+m),一次前缀和

推论 3.二维差分(图中展示的是两种算法的各两种计算方法)

在二维差分中adjacent_difference需要套在一层for循环中,计算行的差分,列的差分需要再加一成for循环后手写d[i][j] = a[i][j] - a[i - 1][j],先计算列差分,再计算行差分.前缀和的话要先计算行,再计算列

推论 4.(同推论 2)

推论 5.异或分,乘法取模分

这个差分是异或差分,前缀和是前缀异或和,和普通的差分,前缀和不同

乘法取模分需要逆元

推论6.(扩展推论2和4)

多重差分

推论 7.差分数组的正负性可以反映原数组的增减性

在排除差分数组的第一位的情况下，差分数组为正数的话，那么像原数组一定是递增的，为负数则递减，为 0 则为相同元素

技巧1：在写题的时候，有些题不是先输入原数组，再构造差分数组，再转回原数组并输出结果的，有时候会直接输入一个差分数组，最后只需要转回原数组

技巧2（P4231）：普通的差分解决的是把数组中一段数同时加一个数，这是一次差分。但是如果要数组中一段数去加一段等差数列，每个数所加的数是不一样的。这时可以反复利用差分的性质，发现原数组的一次差分数组的规律，从而利用二阶差分数组把这个过程优化为在四个位置的运算。复杂度从n*m变为n+m，最后通过两次前缀和还原。

 while (m--) {                    //m在这里，diff是（n+3）
    int l, r, s, e;                //左，右，首项，末项
    cin >> l >> r >> s >> e;
    int d = (e - s) / (r - l);    //公差
    diff[l] += s;                    //四条结论
    diff[l + 1] += d - s;
    diff[r + 1] -= e + d;
    diff[r + 2] += e;
  }

矩阵相乘的妙用 lq2128