在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。1，输入5，   调用upDate(5, 1),把第5位设置为11 2 3 4 50 0 0 0 1计算1-5上比5小的数字存在么？ 这里用到了树状数组的getSum（5） = 1操作，现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。2. 输入2， 调用upDate(2, 1),把第2位设置为11 2 3 4 50 1 0 0 1计算1-2上比2小的数字存在么？ 这里用到了树状数组的getSum（2） = 1操作，现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。3. 输入1， 调用upDate(1, 1),把第1位设置为11 2 3 4 51 1 0 0 1计算1-1上比1小的数字存在么？ 这里用到了树状数组的getSum（1） = 1操作，现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。4. 输入4， 调用upDate(4, 1),把第5位设置为11 2 3 4 51 1 0 1 1计算1-4上比4小的数字存在么？ 这里用到了树状数组的getSum（4） = 3操作，现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。5. 输入3， 调用upDate(3, 1),把第3位设置为11 2 3 4 51 1 1 1 1计算1-3上比3小的数字存在么？ 这里用到了树状数组的getSum（3） = 3操作，现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。6. 0+1+2+1+2 = 6 这就是最后的逆序数

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 #include<stack>10 using namespace std;11 12 const int maxn=500000+5;13 14 int n;15 16 struct node17 {18     int val;19     int pos;20 }a[maxn];21 22 int b[maxn];23 int c[maxn];24 25 bool cmp(node a,node b)26 {27     return a.val<b.val;28 }29 30 int lowbit(int x)31 {32     return x&-x;33 }34 35 int sum(int x)36 {37     int ret=0;38     while(x>0)39     {40         ret+=c[x];41         x-=lowbit(x);42     }43     return ret;44 }45 46 void add(int x,int d)47 {48     while(x<=n)49     {50         c[x]+=d;51         x+=lowbit(x);52     }53 }54 55 int main()56 {57     //freopen("D:\\input.txt","r",stdin);58     while(~scanf("%d",&n) && n)59     {60         for(int i=1;i<=n;i++)61         {62             scanf("%d",&a[i].val);63             a[i].pos=i;64         }65         sort(a+1,a+1+n,cmp);66         for(int i=1;i<=n;i++)67             b[a[i].pos]=i;68         memset(c,0,sizeof(c));69         long long ans=0;70         for(int i=1;i<=n;i++)71         {72             add(b[i],1);73             ans+=i-sum(b[i]);74         }75         printf("%lld\n",ans);76     }77     return 0;78 }