树状数组求排列的逆序数

由于树状数组没有负数节点和0节点，(有些书上说有0节点，是为了方便理解树状数组而假设存在的虚拟节点，)，所以当排列中有负数或0的话，先将他们按照输入顺序标号，再将其从小到大排序，然后以标号为排列查找逆序数。

原理

假设数列为 5 4 3 2 1
5前面比它本身小的数有0个
4前面比它本身小的数有1个
3前面比它本身小的数有2个
2前面比它本身小的数有3个
1前面比它本身小的数有4个
所以他的逆序数为1+2+3+4=10
如果只是单纯的暴利的话，这是一种O(n2)的做法，但是我们有一种更为方便的数据结构—-树状数组，它查询和，修改单点值的复杂度为O(logn)，所以复杂度就降到了O(nlogn)。
下面提供两个代码。

排列不包含0和负数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int c[100005], n;

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

void update(int k, int x)
{
    while (k <= n)
    {
        c[k] += x;
        k += lowbit(k);
    }
}
int getsum(int k)
{
    int sum = 0;
    while (k > 0)
    {
        sum += c[k];
        k -= lowbit(k);
    }
    return sum;
}

int main()
{
    while (scanf("%d", &n) > 0)
    {
        memset(c, 0, sizeof(c));
        long long int ans = 0, t;
        for (int i = 1; i <= n; i++)
        {
            cin >> t;
            update(t, 1);
            ans += i - getsum(t);
        }
        printf("%lld\n", ans);
    }
}

排列为任意数字

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef struct node
{
    int data;
    int id;
}Node;

Node arr[100005];
int c[100005], n;

int cmp(Node a, Node b)
{
    if (a.data != b.data)
        return a.data < b.data;
    return a.id < b.id;
}

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

void update(int k, int x)
{
    while (k <= n)
    {
        c[k] += x;
        k += lowbit(k);
    }
}

long long int getsum(int k)
{
    long long int sum = 0;
    while (k > 0)
    {
        sum += c[k];
        k -= lowbit(k);
    }
    return sum;
}

int main()
{
    while (scanf("%d", &n) > 0)
    {
        memset(c, 0, sizeof(c));
        long long int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &arr[i].data);
            arr[i].id = i;
        }
        sort(arr + 1, arr + n + 1, cmp);
        for (int i = 1; i <= n; i++)
        {
            update(arr[i].id, 1);
            ans += i - getsum(arr[i].id);
        }
        printf("%lld\n", ans);
    }
}