樹狀數組從入門到入墳
一個必備運算
為了方便，以下稱一個二進位數 \(i\) 最低位 \(1\) 的位置為 \(i\) 的 \(\texttt{POS}\)。
如何計算正整數 \(i\) 的 \(\texttt{POS}\) 對應的數（令最低位為第 \(0\) 位，即不是位數而是 \(2\) 的位數次）\(\operatorname{lowbit}(i)\)？
如果了解過枚舉子集應該知道，\(i\operatorname{and}(i-1)\) 是去掉 \(i\) 的 \(\texttt{POS}\) 上的 \(1\)，那麼與 \(i\) 做差，就可以了：
\]
但這樣有兩次減法運算！又丑又慢！
誒它不就一位不同嘛，那用異或就可以了：
\]
這種運算普適性比較強，可以適用於不能出現負數的情況。
有沒有更精簡的運算呢？答案肯定是有的，不妨將 \(i\) 取反得到 \(-i\)，因為電腦存儲用的補碼，而 \(-i\) 的補碼在 \(i\) 的 \(\texttt{POS}\) 處是 \(0\)，之前都是 \(1\)。
加 \(1\) 後，更低位的 \(1\) 全被消掉了，只留下了 \(i\) 的 \(\texttt{POS}\) 處的 \(1\)。而更高位乃至符號位都是不同的，與起來全都是 \(0\)，就得出來了：
\]
形態
可以觀察到，如果令最底層為 \(0\) 層，位置 \(i\) 的結點就位於 \(\log_2\operatorname{lowbit}(i)\) 層。
每個結點的父親是其後面第一個層數大於它的結點。顯然，結點 \(i\) 的父親就是結點 \(i+\operatorname{lowbit}(i)\)。
要具體理解 \(i+\operatorname{lowbit}(i)\) 的話，可以看做去掉最後連續的 \(1\)，在它們前面加一個 \(1\)，比如說 \(1001110_2\to 1010000_2\)。
結點 \(i\) 存儲其子樹 \([i-\operatorname{lowbit}(i)+1,i]\) 的資訊，只不過沒有了懶標記。
這個區間是怎麼來的呢？當然可以看上面那個圖感性理解，但理性分析也可以，數 \(j\) 如果滿足：
- \(j\) 的 \(\texttt{POS}\) 高於 \(i\) 的 \(\texttt{POS}\)，例如 \(i=1001100_2\)，\(j=1001000_2\)。
- 在 \(i\) 的 \(\texttt{POS}\) 之前不同，例如 \(i=1001100_2\)，\(j=1010100_2\)。
- 在 \(i\) 的 \(\texttt{POS}\) 及之前相同且 \(j\) 的 \(\texttt{POS}\) 低於 \(i\) 的 \(\texttt{POS}\)，例如 \(i=1001100_2\)，\(j=1001101_2\)。
以上三種情況不可能存在 \(i\) 這個祖先，可以手推一下感受感受。
等價條件是 \(i-\operatorname{lowbit}(i)>j-\operatorname{lowbit}(j)\)。
單點加區間求和
修改直接向上跳。
對於查詢操作，我們發現這個結構很難快速維護區間資訊，但能快速維護前綴資訊。因為 \(i\) 可以被拆成 \(\operatorname{popcount}(i)\) 個不相同的二的次冪和。每次計算大小最小也就是 \(\operatorname{lowbit}(i)\) 的那棵子樹，然後跳到 \(i-\operatorname{lowbit}(i)\) 結點直到跳到不存在的結點 \(0\) 為止，恰好計算完整個前綴。
區間拆成兩個前綴相減即可。
區間加單點求和。
維護差分數組，即修改操作 \([l,r]\) 在 \(l\) 位置加上，在 \(r+1\) 位置減掉。
位置 \(i\) 的值就是 \([1,i]\) 這個前綴和。
單點加前綴求最值
必須保證最值單調（即最大值只能加非負數，最小值只能加非正數），不然就爆蛋了。
把加法換成取最值即可。
單點加區間求最值
感覺前面那個東西弱爆了，嘗試加強一下。
因為最值沒有可減性，那就從不斷逼近邊界。從 \(r\) 開始，假設當前在 \(i\)，如果 \(i-\operatorname{lowbit}(i)\geq l\) 就減，否則 \(i\) 位置單獨算一下，然後跳到 \(i-1\)。
發現跳 \(O(\log n)\) 次一定能縮小區間的至少一半，所以單次查詢時間複雜度是 \(O(\log^2n)\)。
權值樹狀數組上二分
一種簡單的寫法是先將右端點補齊至二的冪次，然後每次劃分出來的中點加上之前算過的前綴一定也是個前綴。
如果是查詢區間的話可以先將前綴加上，轉化成全局。
P3688 [ZJOI2017] 樹狀數組
如果說正確寫法維護前綴和的查詢操作的本質是將前綴拆成不重合的幾部分加和的話，那錯誤寫法的修改操作的本質就是將前綴拆成不重合的幾部分單獨修改。
如果說正確寫法維護前綴和的修改操作的本質是將所有涉及到的子樹都進行修改的話，那錯誤寫法的查詢操作的本質就是將所有涉及到的子樹加和。
所有錯誤寫法也是不會算重的，對於任意一個修改操作，只會對其前綴影響恰好一次。
那不就是後綴和嗎。
