树状数组

树状数组

1sum(a[1] ~ a[11]) = s[8] + s[10] + s[11]
2sum(a[1] ~ a[5])  = s[4] + s[5]
3sum(a[6] ~ a[11]) = sum(a[1] ~ a[11]) - sum(a[1] ~ a[5])

树状数组统计逆序对

力扣题目,LCR 170. 交易逆序对的总数

 1class BIT {
 2    vector<int> tree;
 3    int n;
 4
 5public:
 6    BIT(int _n) :
 7        n(_n), tree(_n + 1) {}
 8
 9    static int lowbit(int x)
10    {
11        return x & (-x);
12    }
13
14    int query(int x)
15    {
16        int sum = 0;
17        while (x) {
18            sum += tree[x];
19            x -= lowbit(x);
20        }
21        return sum;
22    }
23
24    int range(int l, int r)
25    {
26        return query(r) - query(l - 1);
27    }
28
29    void update(int x, int delta)
30    {
31        while (x <= n) {
32            tree[x] += delta;
33            x += lowbit(x);
34        }
35    }
36};
37
38class Solution {
39public:
40    int reversePairs(vector<int> &record)
41    {
42        int n = record.size();
43        vector<int> mp = record;
44        // 离散化
45        sort(mp.begin(), mp.end());
46        for (int &num : record) {
47            num = lower_bound(mp.begin(), mp.end(), num) - mp.begin() + 1;
48        }
49        // 树状数组统计逆序对
50        BIT bit(n);
51        int ans = 0;
52        for (int i = n - 1; i >= 0; --i) {
53            ans += bit.query(record[i] - 1);
54            bit.update(record[i], 1);
55        }
56        return ans;
57    }
58};