差分詳細(xì)講解(C++)-創(chuàng)新互聯(lián)

每日一句:平凡的我在人多的地方曾極力小心翼翼， 但不知從何時(shí)起 ，我不太在意別人的目光了。比起被人覺得是個(gè)怪人，我現(xiàn)在更害怕浪費(fèi)時(shí)間。

成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的連山網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

差分
  • 一、一維差分
  • 二、二維差分

一、一維差分

差分就是前綴和的逆運(yùn)算,如果你不懂什么是前綴和,看這里->前綴和詳解

數(shù)組a：a[1], a[2], a[3], a[n]
數(shù)組b ： b[1] ,b[2] , b[3], b[i]
使得 a數(shù)組是b數(shù)組的前綴和,b數(shù)組是a數(shù)組的差分
a[i] = b[1] + b[2] + …+ b[i]

數(shù)字來看的話就是這樣的:
a數(shù)組1 3 7 5 2
b數(shù)組1 2 4 -2 -3
Sumb數(shù)組1 1+2 1+2+4 1+2+4-2 1+2+4-2-3
----------也就是1 3 7 5 2跟原數(shù)組還是相同的
a是b的前綴和,b是a的差分.

那么,問題來了,差分有什么用呢?

當(dāng)你把一個(gè)區(qū)間[L,R]的數(shù)都加上或減去某一個(gè)數(shù)x的時(shí)候,該怎末做呢?第一時(shí)間想到的肯定是暴力做法,輸入LR區(qū)間,然后for循環(huán),直接暴力解決,確實(shí)暴力解法能解決很多事情,但是時(shí)間復(fù)雜度很高,為O(n),如果想進(jìn)行m次區(qū)間加上或減去x的操作呢?每次都遍歷LR區(qū)間,那么時(shí)間復(fù)雜度就更高了O(n*m).這個(gè)時(shí)候,就有人對(duì)其優(yōu)化,想出來了一種名為差分的解法,差分解法呢,有一個(gè)公式:[L,R] + X<==>差分?jǐn)?shù)組[L] + X,差分?jǐn)?shù)組[R+1] - X;
那么,這個(gè)公式是怎么來的?
在這里插入圖片描述
下面看一道例題:

輸入一個(gè)長度為 n 的整數(shù)序列。

接下來輸入 m 個(gè)操作，每個(gè)操作包含三個(gè)整數(shù) l,r,c，表示將序列中 [l,r] 之間的每個(gè)數(shù)加上 c。

請(qǐng)你輸出進(jìn)行完所有操作后的序列。

輸入格式

第一行包含兩個(gè)整數(shù) n 和 m。

第二行包含 n 個(gè)整數(shù)，表示整數(shù)序列。

接下來 m 行，每行包含三個(gè)整數(shù) l，r，c，表示一個(gè)操作。

輸出格式

共一行，包含 n 個(gè)整數(shù)，表示最終序列。

數(shù)據(jù)范圍

1≤n,m≤100000, 1≤l≤r≤n, ?1000≤c≤1000, ?1000≤整數(shù)序列中元素的值≤1000

輸入樣例：

—6 3
—1 2 2 1 2 1
—1 3 1
—3 5 1
—1 6 1

輸出樣例：

3 4 5 3 4 2

1.先輸入數(shù)組

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

然后把原數(shù)組a,變成差分?jǐn)?shù)組b

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


	for (int i = 1; i<= n; i++)
	{insert(i, i, a[i]);
	}

對(duì)差分?jǐn)?shù)組進(jìn)行m次操作

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

最后,將差分?jǐn)?shù)組變回原數(shù)組

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

總代碼

#includeusing namespace std;

const int N = 1e6 + 10;

int a[N];

int b[N];

void insert(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++)
	{insert(i, i, a[i]);
	}

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

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


	return 0;
}

題目來源acwing799

二、二維差分

二維差分也就是二維前綴和的逆運(yùn)算,其構(gòu)造差分的過程和構(gòu)造一維差分的過程差不多類似.在這里主要說一下構(gòu)造過程:

void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

標(biāo)紅區(qū)區(qū)域便是x1,y1進(jìn)行區(qū)間加或減操作的區(qū)域

在這里插入圖片描述

黃色和咖啡色區(qū)域便是x2+1,y1和x1,y2+1的區(qū)間,而有x2+1,y2+1的區(qū)間是重疊的部分,也就是說,在b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c;這兩部中,x2+1,y2+1被多減了一次,所以要把這部分還回去,也就是這一步b[x2 + 1][y2 + 1] += c;

在這里插入圖片描述

下面看一到例題

輸入一個(gè) n 行 m 列的整數(shù)矩陣，再輸入 q 個(gè)操作，每個(gè)操作包含五個(gè)整數(shù) x1,y1,x2,y2,c，其中 (x1,y1) 和(x2,y2) 表示一個(gè)子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。

每個(gè)操作都要將選中的子矩陣中的每個(gè)元素的值加上 c。

請(qǐng)你將進(jìn)行完所有操作后的矩陣輸出。

輸入格式

第一行包含整數(shù) n,m,q。

接下來 n 行，每行包含 m 個(gè)整數(shù)，表示整數(shù)矩陣。

接下來 q 行，每行包含 5 個(gè)整數(shù) x1,y1,x2,y2,c，表示一個(gè)操作 。

輸出格式

共 n 行，每行 m 個(gè)整數(shù)，表示所有操作進(jìn)行完畢后的最終矩陣。

數(shù)據(jù)范圍

1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
?1000≤c≤1000,
?1000≤矩陣內(nèi)元素的值≤1000

輸入樣例：

3 4 3

1 2 2 1

3 2 2 1

1 1 1 1

1 1 2 2 1

1 3 2 3 2

3 1 3 4 1

輸出樣例：

2 3 4 1

4 3 4 1

2 2 2 2

代碼

#includeusing namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i<= n; i++)
        for (int j = 1; j<= m; j++)
            scanf("%d", &a[i][j]);

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

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

    for (int i = 1; i<= n; i++)
        for (int j = 1; j<= m; j++)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i<= n; i++)
    {for (int j = 1; j<= m; j++) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}

題目來源acwing800

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：差分詳細(xì)講解(C++)-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://muchs.cn/article34/csphse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、微信小程序、App開發(fā)、移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)站營銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站建設(shè)網(wǎng)站維護(hù)公司