树状数组从入门到入坟
一个必备运算
为了方便，以下称一个二进制数 \(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] 树状数组
如果说正确写法维护前缀和的查询操作的本质是将前缀拆成不重合的几部分加和的话，那错误写法的修改操作的本质就是将前缀拆成不重合的几部分单独修改。
如果说正确写法维护前缀和的修改操作的本质是将所有涉及到的子树都进行修改的话，那错误写法的查询操作的本质就是将所有涉及到的子树加和。
所有错误写法也是不会算重的，对于任意一个修改操作，只会对其前缀影响恰好一次。
那不就是后缀和吗。