image.png
首先树状数组,就是用数组来模拟树形结构.
和「堆」一样，树状数组的 0 号下标不放置元素，从 1 号下标开始使用。
lowbit 函数
这样命名的含义是截取一个正整数的二进制表示里的最低位的 1 和它后面的所有的 0。lowbit 的定义如下：
lowbit(x) = x & (-x);
说明：
这里 x 一定是正整数，即 x >= 1；
这里 & 表示按位与运算；
-x 也可以写成 (~x + 1) ，这里 ~ 表示「按位取反」。这是负数的定义，负数用补码表示，它的值等于这个负数的绝对值按位取反以后再加 11，因此
lowbit(x) = x & (~x + 1);。
单点更新
/**
* 单点更新
*
* @param i 原始数组索引 i
* @param delta 变化值 = 更新以后的值 - 原始值
*/
public void update(int i, int delta) {
// 从下到上更新，注意，预处理数组，比原始数组的 len 大 1，故 预处理索引的最大值为 len
while (i <= len) {
tree[i] += delta;
i += lowbit(i);
}
}
前缀和查询
/**
* 查询前缀和
*
* @param i 前缀的最大索引，即查询区间 [0, i] 的所有元素之和
*/
public int query(int i) {
// 从右到左查询
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
求逆序对的算法题
将离散过的数据,从后往前放进树状数组里,
当第 i 个数的时候,即将放进 树状数组 里的时候,后边比他小的数已经放进他前面的下标里了, 因此只需要把他前面元素的数量加一块,就得到后边有多少比第i个数小的了
