树状数组（Binary Index Tree, BIT）是用用数组来模拟树形结构。最简单的树状数组支持两种操作，时间复杂度均为：
- 单点修改：更改数组中一个元素的值
- 区间查询：查询一个区间内所有元素的和
树状数组-01.png
数组的构建：
int[] tree = new int[len];
求前n项和：
求和时需要如此计算SUM_i=C[i]+C[i-2^(k1)]+C[i-2^(k1)-2^(k2)]+···，那么2^k应该通过i&(-i)。求和就是不断地去掉二进制数最右边的一个1的过程。
public int query(int n) {
int res = 0;
for (int i = n; i > 0; i -= lowbit(i)) res += tree[i];
}
以计算前7项的和为例，最终结果会依次将C[7]、C[6]、C[4]求和。
为什么使用
i&(-i)替代2^k呢？这里利用的负数的存储特性，负数是以补码存储的，对于整数运算
x&(-x)有：
- 当
x为0时，0&0=0- 当
x为奇数时，最后一个比特位为1，取反加1没有进位，故x和-x除最后一位外前面的位正好相反，按位与结果为0。结果为1。- 当
x为偶数，且为2的m次方时，x的二进制表示中只有一位是1（从右往左的第m+1位），其右边有m位0，故x取反加1后，从右到左第有m个0，第m+1位及其左边全是1。这样，x&(-x)得到的就是x。- 当
x为偶数，却不为2的m次方的形式时，可以写作x=y*(2^k)，y的最低位为1，x就是一个奇数左移k位来表示。这时，x的二进制表示最右边有k个0，从右往左第k+1位为1。当对x取反时，最右边的k位0变成1，第k+1位变为0；再加1，最右边的k位就又变成了0，第k+1位因为进位的关系变成了1。左边的位因为没有进位，正好和x原来对应的位上的值相反。二者按位与，得到：第k+1位上为1，左边右边都为0。结果为2^k。总结一下：
x&(-x)，当x为0时结果为0；x为奇数时，结果为1；x为偶数时，结果为x中2的最大次方的因子。public int lowbit(int x) { return x & -x; }
区间求和：
public int query(int a, int b) {
return query(b) - query(a - 1);
}
单点修改：
public void update(int p, int v) {
for (int i = p; i < len; i += lowbit(i)) tree[i] += v;
}
下面针对775. 全局倒置与局部倒置问题使用树状数组进行解决：
class Solution {
public boolean isIdealPermutation(int[] nums) {
int len = nums.length;
int l = 0, g = 0;
// local
for (int i = 1; i < len; i++) {
if (nums[i - 1] > nums[i]) {
l++;
}
}
// global
int[] tree = new int[len + 1];
for (int i = 1; i <= len; i++) {
update(tree, nums[i - 1] + 1, 1);
g += i - query(tree, nums[i - 1] + 1);
}
return l == g;
}
public int lowbit(int x) {
return x & -x;
}
public void update(int[] tree, int p, int v) {
for (int i = p; i < tree.length; i += lowbit(i)) {
tree[i] += v;
}
}
public int query(int[] tree, int n) {
int ans = 0;
for (int i = n; i > 0; i -= lowbit(i)) {
ans += tree[i];
}
return ans;
}
}
参考文献：
