前綴和

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

接下來再輸入 m 個(gè)詢問，每個(gè)詢問輸入一對(duì) l,r。

對(duì)于每個(gè)詢問，輸出原序列中從第 l 個(gè)數(shù)到第 r 個(gè)數(shù)的和。

輸入格式

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

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

接下來 m 行，每行包含兩個(gè)整數(shù) l 和 r，表示一個(gè)詢問的區(qū)間范圍。

輸出格式

共 m 行，每行輸出一個(gè)詢問的結(jié)果。

前綴和思路

原數(shù)組：a[1], a[2],a[3], ... a[n]

前綴和數(shù)組：S[i]=a[1]+a[2]+... a[n]

前綴和一定要從下標(biāo)一開始。這樣有利于處理邊界問題（這樣一來下面用的S[i-1] 不會(huì)出現(xiàn)-1的問題，同時(shí)令S[0]=0）

S[i]=S[i-1]+a[i]

前綴和數(shù)組的作用：快速求出原數(shù)組的某一段的和（[l,r]區(qū)間,l到r），即[l,r]區(qū)間的和為S[r]-S[l-1]?

時(shí)間復(fù)雜度：O(n)

前綴和的過程

1.初始化原數(shù)組

2.初始化前綴和數(shù)組

3.查詢子矩陣

子矩陣的和

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

對(duì)于每個(gè)詢問輸出子矩陣中所有數(shù)的和。

輸入格式

第一行包含三個(gè)整數(shù) n，m，q。

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

接下來 q 行，每行包含四個(gè)整數(shù) x1,y1,x2,y2，表示一組詢問。

輸出格式

共 q 行，每行輸出一個(gè)詢問的結(jié)果。

子矩陣的和的思路

子矩陣的和就是二維的前綴和。

那么，S[i,j]和[X1,Y1],[X2,Y2]的矩陣和就是如下的樣子。

子矩陣的和的思路主要采用了“容斥原理”的思想，即，先不考慮重疊情況，計(jì)算某一內(nèi)容包含的所有對(duì)象的個(gè)數(shù)，再排除重復(fù)計(jì)算的個(gè)數(shù)，使計(jì)算結(jié)果既不遺漏也不重復(fù)。

S[i,j]即為左圖藍(lán)色部分中所有數(shù)的的和為：

S[i,j]=S[i,j?1]+S[i?1,j]?S[i?1,j?1]+a[i,j]

(x1,y1),(x2,y2)子矩陣即為右圖中藍(lán)色部分中所有數(shù)的和為：

S[x2,y2]?S[x1?1,y2]?S[x2,y1?1]+S[x1?1,y1?1]

S[i-1,j-1]是S[i-1,j]和S[i,j-1]兩個(gè)子矩陣相加得到的重復(fù)部分，因此需要消除出去。

S[X1-1,Y1-1]是S[X1-1,Y2]和S[X2,Y1-1]兩個(gè)子矩陣相加得到的重復(fù)部分，因此需要消除出去。

無奈，將就一下，圖片在專欄中被自動(dòng)壓縮就看的不太清了。

子矩陣的和的過程

1.初始化原數(shù)組

2.初始化前綴和數(shù)組

3.查詢子矩陣

二維前綴和和一維前綴和的過程相似，差別主要體現(xiàn)在初始化和查詢上。

困倦，學(xué)一會(huì)兒睡覺去了。

夕弦的圖片由NovalAI生成。