还会接着更新,但很多都会是从洛谷,cf中收集一些题,放入例题栏中

差分:原数组是差分数组的前缀和,换句话说,前缀和逆过来用.
完美的多米诺骨牌

__ 例题四自己第一次写就过了,说实话挺高兴的,但还是得思考原因:
首先看到黑白,自己就想到了二进制编码,然后又看到了题目已经分配好了:0为白色,1为黑色.
然后的内容就是如何如何表示差分.联想到与次数相关最合适,所以,就自己解出来了
all in all,一个抽丝剥茧的过程,每一步都很关键.知道这题用差分同样关键

优点:

//高效进行区间更新：差分数组可以在O(1)的时间复杂度内对原数组的某个区间进行增减操作。
//对于原数组中某个区间的增减操作，只需要在差分数组中对应的两个位置进行增减操作即可，而不需要对整个区间进行遍历。

//减少计算复杂度：在某些情况下，我们需要频繁地对原数组进行区间和计算或者区间更新操作。
//使用差分数组可以将时间复杂度从O(n)降低到O(1)，大大提高了计算效率

代表算法1:(一维)

//b[N]是差分数组.a[N]是原数组,栗子:a[4,7,9,1,2,3] --->>> b[4,7-4,9-7,1-9,2-1,3-2];
//                                                       b[4, 3 , 2 , -8, 1 , 1 ];
void get_dif(int l, int r,int c)
{
    b[l] += c; b[r+1] -= c;
}

代表算法2:(二维)

//首先呢,你可以不有矩阵的基础知识,但你一定要简单模拟一遍
//b[][]是差分数组
void get_marisdif(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]++;
    b[x2+1][y1]--;
    b[x1][y2+1]--;
    b[x2+1][y2+1]++;
}

例题1:acwing算法基础课模板题目

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int a[N],b[N];

void get_dif(int l,int r,int c)
{
    b[l] += c; b[r+1] -= c;
}

int main()
{
    int n,m; cin >> n >> m;

    for(int i = 1 ; i <= n ; i++) cin >> a[i];

    for(int i = 1 ; i  <= n ; i++) get_dif(i,i,a[i]);

    int l,r,c;
    while(m--)
    {
        cin >> l >> r >> c;

        b[l] += c;b[r+1] -= c;


    }

    for(int i = 1; i <= n ; i++) 
    {
        a[i] = a[i-1] + b[i];
        cout << a[i] << " ";
    }

    cout << endl;

    return 0;
}

例题2:AcWing 4262. 空调;
原数组,前缀和数组,差分数组;
只和差分数组有关,

//暴力不能过,而差分能过,只是因为差分数组的一个元素值代表了太多数
//要体会原数组是差分数组的前缀和,自己模拟便理解
//至于为什么前缀可以得到答案

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 100010;

int p[N],b[N];
int n,t;

void get_dif(int l, int r,int c)
{
    b[l] += c;b[r+1] -= c;
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n ; i++ ) cin >> p[i];

    for(int i= 1 ; i <=n  ; i++) {cin >> t;p[i] = p[i] - t;}

    for(int i = 1 ; i <= n ; i++) get_dif(i,i,p[i]);

    int sadd = 0, ssub = 0; 
    for(int i =1  ;  i <= n ; i++)
    {
        if(b[i] > 0) sadd += b[i];
        else ssub += abs(b[i]);
    }
    cout << max(sadd,ssub) << endl;
}

例题三:acwing的算法基础课的矩阵差分,模拟一遍问题就不大.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int L = 1010;

int a[L][L],b[L][L];

void get_mrixdif(int l1,int r1,int l2, int r2,int c)
{
    b[l1][r1] += c;
    b[l2+1][r1] -= c;
    b[l1][r2+1] -= c;
    b[l2+1][r2+1] += c;
}

int main()
{
    int n,m,q;cin >> n >> m >> q;

    for(int i = 1 ; i <= n ; i++) 
        for(int j = 1; j <= m ; j++)    
            cin >> a[i][j];

    for(int i = 1; i <= n ; i++)
        for(int j = 1 ; j <= m ;  j++)
            get_mrixdif(i,j,i,j,a[i][j]);

    int x1,y1,x2,y2,c;    
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2 >> c;

        get_mrixdif(x1,y1,x2,y2,c);
    }

    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m  ; j++)  
        {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
            cout << a[i][j] << " " ;
        }
        cout << endl;
    }

    return 0;
}

例题4:题型:棋盘.蓝桥第十四届题目
哈哈,我还挺高兴的,第一次写就过了,但肯定少不了前面的知识积累啊!!!

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 2010;

int a[N][N],b[N][N];

void change_marixdif(int l1,int r1,int l2,int r2)//奇偶
{
    b[l1][r1]++ ;
    b[l2+1][r1]--;
    b[l1][r2+1]--;
    b[l2+1][r2+1]++;
}

int main()//白为0,黑为1;
{
    int n,m; cin >> n >> m;

    memset(b,0,sizeof b);
    memset(a,0,sizeof a);

    int x1,y1,x2,y2;    
    while(m--)
    {
        cin >> x1 >> y1 >> x2 >> y2;

        change_marixdif(x1,y1,x2,y2);
    }

    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j ++)  
        {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
            if(a[i][j] & 1) cout << 1;
            else cout << 0;
        }
        cout << endl;
    }
}

例题五:第十三届蓝桥省赛题:重新排序
这道题有思路,但第一次没写出来,原因在于不明白代码表达,代码转化能力太弱了!!!
第一次的代码没有用到前缀和,差分更是不知道用到哪一个
说明还没有掌握透例题四哦,其实这道题的差分思路跟例题四很像很像.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

#define int long long

const int N = 100010;

int a[N],b[N],num[N];

void get_diff(int l,int r,int c)
{
    num[l] +=c;num[r+1] -=c;
}

signed main()
{
    int n; cin >> n;

    for(int i = 1 ; i <= n ; i++) 
    {
        cin >> a[i];
        b[i] = b[i-1] + a[i];
    }

    int m ;  cin >> m;
    int l1,r1;
    int sum1 =0,sum2=0;

    while(m--)
    {// 1 3 6  1 2 3
        cin >> l1 >> r1; 

        sum1+=b[r1] - b[l1-1];

        get_diff(l1,r1,1);
    }

    for(int i = 1 ; i <= n ; i++) num[i] += num[i-1];

    sort(a+1,a+1+n);
    sort(num+1,num+1+n);

    for(int i = 1 ; i <= n ; i++)
    {
        sum2 += num[i] * a[i];
    }

    cout << sum2 - sum1 << endl;

    return 0;
}