【leetcode】树状数组逆序

发表于 | 分类于 ，

逆序数，树状数组


描述

逆序数，树状数组

样例

1
2
输入: 5,2,6,1
输出: 2，1，1，0

思路

树状数组是一个数据结构，能很快的求出某一段到某一段的和，求解逆序数注意对下标映射的理解，另外本程序并没有解决有数相等的问题。关于x&(-x)，-x 是x 的补码；补码为取反+1。

变量 二进制
x 1100
-x 0011+1
x&(-x) 0100

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 class BIT{
     vector<int> tree;

 public:
     BIT(int size){
        tree = vector<int>(size,0);
     }

     //return the sum from 1 to idx 
     int read(int idx){
         int sum =0;
         while(idx>0){
             sum += tree[idx];
             idx -= (idx & -idx);
         }
         return sum;
     }

     // return the val in this index ,
     // origin value
     int readSingle(int idx){
         int sum = tree[idx];
         if(idx > 0){
             int z = idx - (idx & -idx);
             idx--;
             while(idx != z){
                 sum -= tree[idx];
                 idx -= (idx & -idx);
             }
         }
         return sum;
     }

     void update(int idx,int val){
         while(idx <= (int)tree.size()-1){
             tree[idx] += val;
             idx += (idx & -idx);
         }
     }
 
 };
typedef struct P{
    int val;
    int pos;
}P ;

int cmp(const void * a,const void *b){
    return (*(P*)a).val - (*(P*)b).val;
}

 class Solution {
 public:
     vector<int> countSmaller(vector<int>& nums) {
         struct P * s =  (struct P *) malloc(sizeof(struct P)* (nums.size()));
         for(int i=1;i<=(int)nums.size();i++){
            s[i].pos  = i;
            s[i].val = nums[i-1];
         }
         qsort(s+1,nums.size(),sizeof(s[0]),cmp);

         vector<int> ds(nums.size()+1,0);
         for(int i=1;i<= (int)nums.size();i++){
            ds[s[i].pos] = i;
         }
         vector<int> res(nums.size(),0);
         BIT bit(nums.size()+1);
        for(int i= nums.size();i>=1;i--){
           res[i-1] = bit.read(ds[i]);
           bit.update(ds[i],1);
        }
        return res;
     }

 };

参考

原题链接
参考链接
参考链接