树状数组

定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.

例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。

将34转为二进制,为0010 0010,这里的"最后一个1"指的是从${\displaystyle 2^{0}}$位往前数,见到的第一个1,也就是${\displaystyle 2^{1}}$位上的1.

程序上，((Not I)+1) And I表明了最后一位1的值,

仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2).

Lowbit的一个简便求法:（C++）

int lowbit(int x)
{
    return x&(-x);
}

定义一个数组 BIT，用以维护${\displaystyle A}$的前缀和，则:

${\displaystyle BIT_{i}=\sum _{j=i-lowbit(i)+1}^{i}A_{j}}$

具体能用以下方式实现：（C++）

void build()
{ 
    for (int i = 1; i <= MAX_N; i++)
    {
        BIT[i] = A[i - 1];
        for (int j = i - 2; j >= i - lowbit(i); j--)
            BIT[i] += A[j];
    }
}
//注：这里的求和将汇集到非终端结点（D00形式）
//BIT中仅非终端结点i值是 第0~i元素的和
//终端结点位置的元素和，将在求和函数中求得
//BIT中的index，比原数组中大1

假设现在要将${\displaystyle A[i]}$的值增加delta，

那么，需要将${\displaystyle BIT[i]}$覆盖的区间包含${\displaystyle A[i]}$的值都加上delta，

这个过程可以写成递归，或者普通的循环。

需要计算的次数与数据规模N的二进制位数有关，即这部分的时间复杂度是O(LogN)

修改函数的C++写法

void edit(int i, int delta)
{
    for (int j = i; j <= MAX_N; j += lowbit(j))
        BIT[j] += delta;
}

假设我们需要计算${\displaystyle \sum _{i=1}^{k}A_{i}}$的值。

1. 首先,将ans初始化为0，将i初始化为k
2. 将ans的值加上BIT[i]
3. 将i的值减去lowbit(i)
4. 重复步骤2～3，直到i的值变为0

求和函数的C/C++写法

int sum (int k)
{
    int ans = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}

初始化复杂度最优为${\displaystyle O(N)}$

单次询问复杂度${\displaystyle O(\log N)}$，其中N为数组大小

单次修改复杂度${\displaystyle O(\log N)}$，其中N为数组大小

空间复杂度${\displaystyle O(N)}$

逆序对数是一个数列中在它前面有比它大的个数。如4312的逆序对数是0+1+2+2=5。

可以先把数列中的数按大小顺序转化成${\displaystyle 1}$到${\displaystyle n}$的整数，使得原数列成为一个${\displaystyle 1,2,...,n}$的排列${\displaystyle P}$，创建一个树状数组，用来记录这样一个数组${\displaystyle A}$（下标从1算起）的前缀和：若排列中的数${\displaystyle i}$当前已经出现，则${\displaystyle A[i]}$的值为${\displaystyle 1}$，否则为${\displaystyle 0}$。初始时数组${\displaystyle A}$的值均为${\displaystyle 0}$，从排列中的最後一个数开始遍历，每次在树状数组中查询有多少个数小于当前的数${\displaystyle P[j]}$（即用树状数组查询数组${\displaystyle A}$目前${\displaystyle P[j]-1}$个数的前缀和）并加入计数器，之后对树状数组执行修改数组${\displaystyle A}$第${\displaystyle P[j]}$个数值加${\displaystyle 1}$的操作。