非常深刻
一個必備運算
為了友善，以下稱一個二進制數 \(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\operatorname{and}(i-1))
\]
但這樣有兩次減法運算！又醜又慢！
诶它不就一位不同嘛，那用異或就可以了：
\[i\operatorname{xor}(i\operatorname{and}(i-1))
\]
這種運算普适性比較強，可以适用于不能出現負數的情況。
有沒有更精簡的運算呢？答案肯定是有的，不妨将 \(i\) 取反得到 \(-i\)，因為計算機存儲用的補碼，而 \(-i\) 的補碼在 \(i\) 的 \(\texttt{POS}\) 處是 \(0\)，之前都是 \(1\)。
加 \(1\) 後，更低位的 \(1\) 全被消掉了，隻留下了 \(i\) 的 \(\texttt{POS}\) 處的 \(1\)。而更高位乃至符号位都是不同的，與起來全都是 \(0\)，就得出來了：
\[i\operatorname{and}-i
\]
形态
可以觀察到，如果令最底層為 \(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] 樹狀數組
如果說正确寫法維護字首和的查詢操作的本質是将字首拆成不重合的幾部分加和的話，那錯誤寫法的修改操作的本質就是将字首拆成不重合的幾部分單獨修改。
如果說正确寫法維護字首和的修改操作的本質是将所有涉及到的子樹都進行修改的話，那錯誤寫法的查詢操作的本質就是将所有涉及到的子樹加和。
所有錯誤寫法也是不會算重的，對于任意一個修改操作，隻會對其字首影響恰好一次。
那不就是字尾和嗎。