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

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

前綴和

• 前言
• 一、一維前綴和
• • 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.前綴和是什么？

用一個簡單的列子去介紹

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

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;
	}

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

暴力會超時。

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

如何利用前綴和去求區(qū)間大小呢？
有一個公式：s[r] - s[l - 1]。
就是這個公式，他的時間復(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]，這個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()//前綴和寫法
{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ǔ)上實現(xiàn)的，唯一不同的就是，這個是二維的。

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開始
這樣理解可能有點困難，畫個圖就知道了。

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

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

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

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

由此可以看出，在計算s[i,j]的和的時候，是不是把區(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.子矩陣的和

---

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

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

新聞標(biāo)題：前綴和（C++）實現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://weahome.cn/article/iepho.html