树状数组（BIT）
码量小，常数小。
支持单点修改，前缀查询。
区间修改+区间查询
区间修改可以使用差分解决。
对于区间查询，可以先考虑前缀查询：
记差分数组为\(d_i\)，原数组为\(a_i\)，前缀和数组为\(S_i\)。
\(a_i\ =\ \sum_{j=1}^{i} d_j\)，\(S_i\ =\ \sum_{j=1}^{i} a_j\)。
则\(S_i\ =\ \sum_{j=1}^{i} (i-j+1)d_j\)。
展开得\(S_i\ =\ (i+1)\sum_{j=1}^{i} d_j-\sum_{j=1}^{i} j\times d_j\)。
所以维护两个树状数组，分别记录\(d_i\)和\(i\times d_i\)的值。
树状数组上二分
给出一个序列，单点修改，前缀查询第一个前缀和大于\(k\)的位置。
对于此类问题，直接二分的复杂度是\(O(log^2 n)\)的。
我们可以使用树状数组上二分，复杂度：\(O(log n)\)。
说是二分，其实二分也没太大关系。
从高到低枚举 2 的次幂，不断向前跳，最终得到答案。
权值树状数组
当值域较小时，可以直接在值域上开树状数组。
否则也可以离散化。
权值树状数组可以解决以下问题：
1.插入一个数，删除一个数
2.查询前缀有多少数大（小）于当前值
3.查询全局（前缀）第\(k\)大（小）值（树状数组二分）
高维树状数组
比较少见，更多用于解决\(k\)维偏序和\(k\)维数点。
\(k\)维树状数组的时间复杂度：\(O(log^k n)\)。