算法笔记求序列A每个元素左边比它小的数的个数(树状数组和离散化)

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 using namespace std ;

 const int N =  ;

 struct node{

     int val,pos ;

 }tmp[N];

 int a[N] ;//离散化后的原始数组

 int c[N] ;//树状数组 

 bool cmp(node st1,node st2){

     return st1.val < st2.val ;

 }

 int lowbit(int x){//取得最右边的一个1

     return x&(-x) ;

 }

 int getSum(int x){//区间1~x的和 log(N)

     int sum =  ;

     for(int i=x;i>;i-=lowbit(i)){

         sum += c[i] ;

     }

     return sum ;

 }

 void update(int x,int v){//单点更新 log(N)

     for(int i=x;i<=N;i+=lowbit(i)){

         c[i] += v ;

     }

 }

 int main(){

     int n, x ;

     cin >> n ;

     memset(c,,sizeof c) ;

     for(int i=;i<n;i++){

         cin >> tmp[i].val ;

         tmp[i].pos = i ;

     }

     sort(tmp,tmp+n,cmp) ;

     for(int i=;i<n;i++){

         if(i== || tmp[i-].val != tmp[i].val)

             a[tmp[i].pos] = i +  ;//离散化

         else{

             a[tmp[i].pos] = a[tmp[i-].pos] ;

         }

     } 

     for(int i=;i<n;i++){

         update(a[i],) ;

         cout << getSum(a[i]-) << endl ;

     }

     return  ;

 } 

算法笔记求序列A每个元素左边比它小的数的个数(树状数组和离散化)的相关教程结束。