每日一句：真正讓人變好的選擇過(guò)程都不會(huì)很舒服，所以人們明知道什么都不做，會(huì)比較輕松，但依舊選擇追逐夢(mèng)想。

“只有客戶發(fā)展了，才有我們的生存與發(fā)展！”這是創(chuàng)新互聯(lián)的服務(wù)宗旨！把網(wǎng)站當(dāng)作互聯(lián)網(wǎng)產(chǎn)品，產(chǎn)品思維更注重全局思維、需求分析和迭代思維，在網(wǎng)站建設(shè)中就是為了建設(shè)一個(gè)不僅審美在線，而且實(shí)用性極高的網(wǎng)站。創(chuàng)新互聯(lián)對(duì)網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、網(wǎng)站開(kāi)發(fā)、網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站優(yōu)化、網(wǎng)絡(luò)推廣、探索永無(wú)止境。

前綴和

• 前言
• 一、一維前綴和
• • 1.前綴和是什么？
  • 2.暴力做法
  • 3.前綴和求區(qū)間大小
  • • 3.1如何構(gòu)成前綴和的形式？
  • 4.完整代碼
• 二、二維前綴和
• • 1.基本思路
  • 2.完整代碼

---

前言

原數(shù)組: a[1], a[2], a[3], a[4], a[5], …, a[n]
前綴和: S[i] = a[1] +a[2] + a[3] + … + a[i]
前綴和能夠快速的求出某一區(qū)間的和。

詳細(xì)看下面的介紹。

一、一維前綴和 1.前綴和是什么？

用一個(gè)簡(jiǎn)單的列子去介紹

原數(shù)組: a[1], a[2], a[3], a[4], a[5], …, a[n]
前綴和: s[i] = a[1] + a[2] + a[3] + … + a[i]
前綴和就是用一個(gè)數(shù)組s去存數(shù)組a的前n項(xiàng)的和。
s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]
s[n] = a[i] + a[2] + a[3] + …+a[n]
這樣s[n]對(duì)應(yīng)的就是a[1]—a[n]的和，s的每一項(xiàng)都這樣對(duì)應(yīng)，就構(gòu)成了前綴和。
注：前綴和的下標(biāo)一定要從1開(kāi)始。

2.暴力做法

int n, m;
	cin >>n >>m;
	int sum = 0;
	for (int i = 1; i<= n; i++)
	{cin >>a[i];
	}
	while (m--)
	{int l, r;
		cin >>l >>r;
		sum = 0;
		for (int i = l; i<= r; i++)
		{	sum += a[i];
		}
		cout<< sum<< endl;
	}

這個(gè)就是用暴力的方法去做，也能求出區(qū)間[L,R]的和，但他的時(shí)間復(fù)雜度為O(n)那么當(dāng)數(shù)據(jù)過(guò)于龐大的時(shí)候就會(huì)造成超時(shí)的情況。

暴力會(huì)超時(shí)。

3.前綴和求區(qū)間大小

如何利用前綴和去求區(qū)間大小呢？
有一個(gè)公式：s[r] - s[l - 1]。
就是這個(gè)公式，他的時(shí)間復(fù)雜度O(1)，這就要比暴力的做法快上很多了。

3.1如何構(gòu)成前綴和的形式？

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

s[1] = s[0] + a[1];
s[2] = s[1] + a[2];
s[3] = s[2] + a[3];
s[n] = s[n - 1] + a[n]
去遍歷a數(shù)組，把當(dāng)前a[n]的數(shù)加上s[n-1]的數(shù)，就能得到s[n]，這個(gè)s[n]就是a[1，n]的和。

4.完整代碼

#includeusing namespace std;

const int N = 1e6 + 10;

int a[N],s[N];
//int main()//暴力做法
//{//	int n, m;
//	cin >>n >>m;
//	int sum = 0;
//	for (int i = 1; i<= n; i++)
//	{//		cin >>a[i];
//	}
//	while (m--)
//	{//		int l, r;
//		cin >>l >>r;
//		sum = 0;
//		for (int i = l; i<= r; i++)
//		{//			sum += a[i];
//		}
//		cout<< sum<< endl;
//	}
//	return 0;
//}
int main()//前綴和寫(xiě)法
{int n, m;
	cin >>n >>m;
	for (int i = 1; i<= n; i++)
	{cin >>a[i];
	}

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

	while (m--)
	{int l, r;
		cin >>l >>r;
		cout<< s[r] - s[l - 1]<< endl;
	}

	return 0;
}

例題acwing795.前綴和

二、二維前綴和 1.基本思路

二維前綴和是建立在一維前綴和的基礎(chǔ)上實(shí)現(xiàn)的，唯一不同的就是，這個(gè)是二維的。

s[1][1] = s[0][1] + s[1][0] - s[0][0] + a[1][1];
s[2][2] = s[1][2] + s[2][1] - s[1][1] + a[2][2];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
注：下標(biāo)從1開(kāi)始
這樣理解可能有點(diǎn)困難，畫(huà)個(gè)圖就知道了。

標(biāo)紅的區(qū)域代表的就是區(qū)間[i-1,j-1]的的和

標(biāo)綠的區(qū)域就是區(qū)間[i-1,j]的和

標(biāo)藍(lán)的區(qū)域就是區(qū)間[i,j-1]的和

這個(gè)整體代表的就是區(qū)間[i,j]的和

由此可以看出，在計(jì)算s[i,j]的和的時(shí)候，是不是把區(qū)間s[i-1,j-1]多算了一次，所以應(yīng)該把s[i-1,j-1]減去一次，就能得到區(qū)間s[i,j]正確的區(qū)間和了。

2.完整代碼

#includeusing namespace std;

const int N = 1e3 + 10;

int a[N][N], s[N][N];


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++)
		{	s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

		}
	}

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

		cout<< s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]<< endl;
	}

	return 0;
}

例題acwing796.子矩陣的和

---

以上就是對(duì)前綴和的介紹，希望對(duì)大家有幫助。

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

文章名稱：前綴和（C++）實(shí)現(xiàn)-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://vcdvsql.cn/article40/iepho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站制作、定制開(kāi)發(fā)、標(biāo)簽優(yōu)化、網(wǎng)站建設(shè)

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)