4小時后開始周賽，雙周賽依舊穩(wěn)定兩題，第三題用例全過，但是超時了，但是學到了新知識差分，感覺很神奇。

原數(shù)組a的差分數(shù)組是[a1,a2-a1,a3-a2...]

人話就是，每一個位置都是當前位置和前一個位置的差值，所以原數(shù)組的信息不會丟失。

其實還是有信息丟失的，差分數(shù)組要還原的話依賴于順序，是順序提供了額外的信息。

然后神奇的地方來了，當對原數(shù)組某個區(qū)間的元素執(zhí)行加減操作時，這個操作體現(xiàn)在差分數(shù)組上就只是b[l]+x,b[r+1]-x(b是差分數(shù)組……

Why?這很好證明，因為(l,r)的元素都是原數(shù)組里兩個數(shù)的差值，這兩個數(shù)同時加上或減去一個數(shù)，并不改變結果。

我理解了，我震驚了。這是哪個天才想出來的，太優(yōu)雅了，變化了的信息只在兩個位置存儲，還原的時候是計算前綴和，實際上是等于某個位置的元素在給其它位置的元素提供信息，用這種方式把冗余的部分優(yōu)化掉了。

它的底層思想，就是在去除重復的部分。這就是我做T3時一直在尋找的東西，既然每一個位置都是一樣的變化，那我為什么非要真的在每個位置都執(zhí)行操作，能不能用某種方式只記錄變化的區(qū)間？我沒想出來，但是這種方式真的存在！

有點熟悉。字典樹也是把重復部分提取出來，動態(tài)規(guī)劃也是把重復的計算優(yōu)化……

好像窺探到一點點算法的本質了。