luogu1908 逆序对树状数组

题目大意：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。求一段序列的逆序对数。

对于一个数组T，其一个点的值为值与该点下标相等的A序列中点的个数。对T维护一个树状数组C。对原始序列A，从后往前扫描i，每次运用树状数组的求前缀和操作查询比A[i]小的数字有几个（因为是倒序循环，所以得到的数字所对应的A序列中的点j都是大于i的）（*），然后运用树状数组的更新操作将树状数组点T[A[i]]的值加1。最后输出（*）的总和。

注意事项：

由于树状数组是在值域上建立的，所以N是输入值的最大值，而不是个数。
Query a[i]时，Query(a[i]-1)，而不是Query(a[i])。否则两个值相等也被算上了。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 40010, MAX_VALUE = 1000000, INF = 0x3f3f3f3f;
int C[MAX_VALUE], A[MAX_N];
int totN, totValue;

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

int Sum(int p)
{
    int sum = 0;
    while (p)
    {
        sum += C[p];
        p -= Lowbit(p);
    }
    return sum;
}

void Update(int p, int delta)
{
    while (p <= totValue)
    {
        C[p] += delta;
        p += Lowbit(p);
    }
}

int main()
{
    totValue = -INF;
    scanf("%d", &totN);
    for (int i = 1; i <= totN; i++)
    {
        scanf("%d", i + A);
        totValue = max(totValue, A[i]);
    }
    int ans = 0;
    for (int i = totN; i >= 1; i--)
    {
        ans += Sum(A[i] - 1);
        Update(A[i], 1);
    }
    printf("%d
", ans);
    return 0;
}

luogu1908 逆序对 树状数组

luogu1908 逆序对树状数组