樹狀數組進階（1）
*前置知識：樹狀數組，如果沒有學過請右轉這篇文章：傳送門，前綴和，差分。
*本文代碼均未經編譯，如有錯誤請指出。
*前排cqy,826755370，喜歡EXO，bigbang，BTS，ikon，nine percent，本命世勳。
引入
大家學了線段樹與樹狀數組後，一定會覺得樹狀數組比線段樹好寫（背）多了，常數也小多了（分析lowbit操作，每次操作中每個節點被訪問的概率是1/2,所以常數是1/2）但是美中不足的是樹狀數組不能區間修改+區間查詢啊。事實上，樹狀數組可以做到這些，還可以查詢第k大（小）值。
1、最簡單的單點修改+區間查詢
這個就不要我講了吧，直接上代碼:
2、 稍微難一點點的區間修改+單點0查詢
這裡用的是差分的思想。
我們設原數組為a，則我們需要維護一個差分數組delta： delta[i]=a[i]-a[i-1]delta[i]=a[i]a[i1]
那麼我們可以得到： $a[i]=\sum_{j=1}^idelta[j]
現在a[i]被表達成了一個數組內連續的幾個元素的，這樣我們就解決了查詢的問題，那麼我們該如何修改呢？
當我們需要將區間[l,r]上的每個數都加上x時，因為d數組是個差分數組，所以我們可以直接在樹狀數組上將delta[l]加上x，delta[r+1]減去x即可，代碼如下：
重點來了！
3、區間修改+區間查詢
我們還是需要引入delta數組，這裡的delta[i]表示區間a[i...j]都需要加上的值的和。那麼當我們需要將區間[l,r]上的每個數都加上x時，我們還是可以直接在樹狀數組上將delta[l]加上x，delta[r+1]減去x。
那麼問題來了，如何查詢區間[l,r]的和？
我們設a[1...i]的和為sum[i]，根據delta數組的定義，則：
這樣我們就不難看sum[i]是由哪三個部分組成的了。我們需要用一個asum數組維護a數組的前綴和，delta1與delta2兩個樹狀數組，delta1維護delta數組的和，delta2維護delta[i]*i的和，代碼如下：
等等……線段樹不是還能查最大最小值嗎，事實上樹狀數組也能查。
4、區間最值
哦，我知道了，我來建樹：
如果你是這麼寫的，那麼恭喜你……寫錯了。
以下內容有些難理解，先放一張圖：
我們回想一下，當初剛學樹狀數組時為什麼很多人總會說樹狀數組不能用來求最值。那是因為樹狀數組可以看作是一種前綴和，求和時可以用ans=ans[r]-ans[l-1]的性質，但是求最值無法滿足這種減法的性質。分析一下我們剛才的代碼，這麼寫也不是不對，而是每次查詢前都必須初始化，時間複雜度難以接受，讓我們換一種寫法試一試：
現在更新完某個數，之前的元素的值都是正確的了，顯而易見，建樹的時間複雜度是O(nlogn)的。
那麼我們該如何修改呢？當然不能在父親節點上直接修改啦（手動滑稽），換了一種建樹的方式就是為了維護c數組的正確性，修改同樣也要保證c數組的正確性，那麼在更新父親節點時，我們就需要查詢它所有的兒子節點，代碼如下：
不難發現，每層循環都是lowbit操作，時間複雜度為O（王逸松）O（log(n)*log(n)),其實也沒多慢，當n=1e5時，logn約等於16,就把一個logn當成常數看，線段樹常數也挺大的啊，樹狀數組代碼量還這麼少。
修改是修改完了，那麼問題來了，我們該如何查詢？
假設當前查詢的區間是[l,r]，那麼我們從r到l對每一個c數組的元素所控制的葉子節點進行判斷。假設現在進行到了第i項，那麼顯然易得（看圖）：該數控制的a數組的元素是 [i-lowbit(i)+1,i]。設L=i-lowbit(i)+1,R=i。如果l<=L<=r那麼就將c[L]加入最值的判斷中，接著L--……，否則的話就只對第R個元素加入，然後R--……，代碼如下：
顯然，時間複雜度是 O(logn*logn)O(lognlogn) 的。
完整代碼如下：
5、二維情況下的樹狀數組
*單點修改+區間查詢 這個我並不想講，唯一需要注意的點寫在注釋裡了，直接上代碼：
*區間修改+單點查詢 在開始之前，我們先回想一下二維的前綴和如何求和：
這個應該沒什麼問題吧？
那麼我們和一維情形一樣，開一個差分數組delta。
思路到此結束，希望大家可以自己寫代碼。
區間修改+區間查詢 這裡只給出一句話思路，希望大家自己思考，寫出代碼。
思路：將以上式子變形成類似一維情形下最終得到的式子。
區間最值 有這麼毒瘤的題目嗎……
完結撒花！★,°:.☆(￣▽￣)/$:.°★ 。
本文發布於洛穀日報，特約作者：Chanis
原文地址：https://www.luogu.org/blog/Chanis/super-BIT