前綴和

前綴和：一段序列里的前n項(xiàng)和

給出n個(gè)數(shù)，在給出q次問(wèn)詢，每次問(wèn)詢給出L、R，快速求出每組數(shù)組中一段L至R區(qū)間的和

給出一段數(shù)組，每次問(wèn)詢?yōu)榍蟪鰈到r區(qū)間的和

普通方法：L到R進(jìn)行遍歷，那么在每次求區(qū)間和的過(guò)程中時(shí)間復(fù)雜度為O(n)，q次問(wèn)詢時(shí)間復(fù)雜度為O(q*n)

前綴和：建立前綴和數(shù)組，sum[i]=sum[i-1]+arr[i]。（i-1存在越界的問(wèn)題，所以i從1開(kāi)始遍歷）

? ? ? ? ? ? ? 計(jì)算L到R的區(qū)間和，包括arr[L]和arr[R]兩個(gè)值（邊界值），區(qū)間和=arr[R]-arr[L-1]

? ? ? ? ? ? ? 時(shí)間復(fù)雜度從O(q*n)降至O(q*1)

二維前綴和

二維前綴和數(shù)組是原數(shù)組它本身位置的數(shù)及其左上角全部的數(shù)

二維前綴和的應(yīng)用：求二維數(shù)組中arr[x1][y1]到arr[x2][y2]區(qū)間內(nèi)的數(shù)之和?

差分

給出n個(gè)數(shù)，再給出q次問(wèn)詢，每次問(wèn)詢給出L、R、X，要求在L到R上每一個(gè)值都加上X，直到最后輸出這個(gè)數(shù)組?

普通方法：遍歷，時(shí)間復(fù)雜度為O(q*n)

差分：建立差分?jǐn)?shù)組，difference[i]=arr[i]-arr[i-1]，arr[i]=difference[i]+arr[i-1]。

????????（同樣i從1開(kāi)始遍歷）

? ? ? ? ? 時(shí)間復(fù)雜度從O(q*n)降至O(q*1)

數(shù)組arr

1

1

1

1

1

1

差分?jǐn)?shù)組difference

1

0

0

0

0

0

此時(shí)，L=2，R=4，X=1

操作方式：difference[L]=difference[L]+X，影響L之后的數(shù)字

? ? ? ? ? ? ? ? ? difference[R+1]=difference[R+1]-X，避免影響R+1以及之后的數(shù)字

操作后的差分?jǐn)?shù)組difference

1

1

0

0

-1

0

還原后的數(shù)組arr

1

2

2

2

1

1

二維差分

一維差分修改差分?jǐn)?shù)組中的某個(gè)數(shù)，影響的是原數(shù)組它本身及其之后的數(shù)

二維差分修改差分?jǐn)?shù)組中的某個(gè)數(shù)，影響的是原數(shù)組它本身及其右下角全部的數(shù)

二維差分的應(yīng)用：對(duì)以?x1, y1?為左上角，?x2, y2?為右下角的矩陣插入一個(gè)值 / 修改值