树状数组
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};