python/TangDou/AcWing/BIT/788_树状数组+线段树.md

##[$AcWing$ $788$. 逆序对的数量](https://www.acwing.com/problem/content/790/)

### 一、题目描述
给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i<j$
 且 $a[i]>a[j]$，则其为一个逆序对；否则不是。

 **输入格式**
第一行包含整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，表示整个数列。

**输出格式**
输出一个整数，表示逆序对的个数。


**数据范围**
$1≤n≤100000$，数列中的元素的取值范围 $[1,10^9]$

**输入样例：**
```cpp {.line-numbers}
6
2 3 4 5 6 1
```
**输出样例：**
```cpp {.line-numbers}
5
```

### 二、前导知识

- **如何获取第几大+原始位置的对应关系数组?**

```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 500010;
int n;
int a[N], b[N];

// 输出原数组
void out() {
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts("");
}

// 功能:排序办法
// ①、数小的在前面
// ②、如果数一样大，序号小的在前
bool cmp(int x, int y) {
    if (a[x] == a[y]) return x < y;
    return a[x] < a[y];
}

// 【方法1】
void func1() {
    cin >> n;

    // ① 初始化                 ：       b[i]=a[i]
    // ② 排序(小的在前，大的在后) :        a[]
    // ③ 每个b[i]通过二分,在排序后的a[]中查找位置，记录b[i]=找到的位置
    // ④ a[]数组被重新由小到大排序
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

    // 输出原始数组
    out();

    // 原始数组由小到大排序
    // ① 由小到大排序,不用加什么greater<int>(),代码更简单
    // ② 只有由小到大排序，后面使用二分进行数值查询位置时，才能使用lower_bound二分方法
    sort(a + 1, a + n + 1);

    // 离散化，遍历原始数组b[i],找出它的排名，即b[2]=3表示第2个输入的是排名第3的
    // 这里的离散化没有用到去重，如果需要去重，参考：788_Unique.cpp
    for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + n + 1, b[i]) - a;

    // 倒序，由大到小(视业务调整)
    for (int i = n; i; i--) printf("%d ", b[i]);
}

// 【方法2】
void func2() {
    cin >> n;

    // ① 初始化                     ：b[i]=i
    // ② 排序(小的在前，大的在后)    : b[]
    // ③ a[]数组不动
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = i;

    // 输出原始数组
    out();

    // 对b[]排序
    sort(b + 1, b + n + 1, cmp);

    // 倒序，由大到小(视业务调整)
    for (int i = n; i; i--) printf("%d ", b[i]);
}

/*
  原始数组    10 8 7 9 4
  输出        1 4 2 3 5
  含义：
  （1）最大的是原始数组的a[1]=10
  （2）次大的是原始数组的a[4]=9
  （3）三大的是原始数组的a[2]=8
   ...
*/
int main() {
    // 调用方法1进行测试
    freopen("788.in", "r", stdin);
    func1();
    puts("");

    // 在第二次重定向时修改一下cin的状态
    cin.clear();
    puts("");

    // 调用方法2进行测试
    freopen("788.in", "r", stdin);
    func2();
    puts("");

    return 0;
}
```

- **为什么不喜欢使用结构体进行描述信息?**
主要是因为我们想使用一种通用的办法：**排序+离散化+二分** 来获取对应关系数组,这时朴素的数组比较方便，带结构体的数组不太好用。


### 二、树状数组解法

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
typedef long long LL;
int a[N], b[N];
int n;

int tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL ans;
int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + 1 + n, b[i]) - a;

    for (int i = 1; i <= n; i++) {
        add(b[i], 1);
        ans += sum(n) - sum(b[i]);
    }
    printf("%lld", ans);
    return 0;
}

```
### 三、$d$数组的作用
数组$a[]$中的每个元素$a[i]$有三个属性：

- ① 数值    $value$
- ② 整体排名 $rank$ (由大到小排序)
- ③ 原始位置 $pos$

**当我们求逆序对时，只关心 ② 和 ③。 ① 在这里是一个临时的概念，它的存在导致可以求出整体的排名 ②**

$d[]$记录的就是 ② 整体的排名 $rank$ + ③ 原来的位置 $pos$

比如：$d[x]=y$ 表示排名第$x$位的数，原始位置是$y$

**$Q$: 排名数组$d[]$的构建步骤？**
$A$:
- 随着$a[i]$读入，记录$d[i] = i$ ,即记录输入序号，当比较数值一样时，用来判断哪个在前
- 实现比较函数 $cmp$, 如果值不一样，值大的在前；如果值一样，则输入序号大的在前
- $sort(d+1,d+1+n,cmp)$ 调用$STL$+自定义$cmp$ 对$d$数组进行排序,最终的排序结果如下面的栗子：

**输入**
$a[]$ 值       `4 2 3 5 1`
$d[]$ 序号     `1 2 3 4 5`

**结果**
$a[]$ 值       `4 2 3 5 1`
$d[]$ 序号     `4 1 3 2 5`

可以清楚看出：
- 原数组没有改变
- $d[1]=4$,表示第$1$名，值最大的，在$a[]$中第$4$个位置上，最大值$=a[d[1]]=a[4]=5$
    $d[2]=1$,表示第$2$名，值次大的，在$a[]$中第$1$个位置上，次大值$=a[d[2]]=a[1]=4$
        ....

**算法步骤**：
1、排名由高到低，逐个让每个数字下场,也就是 **大的数字先入场**，占领它在原始数组中的位置
2、当某个数字下场时，检查它左侧(也就是号比自己小的),现在已经有多少个数字存在,这此数字都符合一个特点：
**数比自己大,号比自己小**,也就是 **逆序对的数量**。


### 四、树状数组的作用
就是可以维护一个 **动态前缀和** ,这是我起的名字，不一定准确，但事就是这么个事。普通前缀和适合于静态数组，像这样一会加进来一个，就需要计算一下前缀和，一会又加进来一个，还想算前缀和的，树状数组的优势就来了，虽然达不到$O(1)$,但$O(logN)$也是很不错的运算速度了。

### 五、疑问

**是不是可以最大排序向左看，最小排序向右看呢？需要测试一下**

答案是一样可以$AC$！原理是一样的，从本质上说应该没有大的在前快，因为需要多计算一下$sum$,但实测效果两者基本一致。

### 六、线段树解法
```cpp {.line-numbers}
// 权值线段树解法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 5e5 + 10;
int a[N], b[N];
int n;

// 线段树区间和模板
#define ls u << 1
#define rs u << 1 | 1

struct Node {
    int l, r; // 范围
    int sum;  // 区间内数字个数
} tr[N << 2]; // 4倍空间

// 创建
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
}

// 向上更新统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

// 修改点的值
void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].sum += v;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid)
        modify(ls, x, v);
    else
        modify(rs, x, v);
    pushup(u);
}

// 查询区间和
int query(int u, int l, int r) {
    if (l > r) return 0;
    if (tr[u].l == l && tr[u].r == r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    if (mid < l) return query(rs, l, r);
    if (r <= mid) return query(ls, l, r);
    return query(ls, l, mid) + query(rs, mid + 1, r);
}

LL ans;

int main() {
    cin >> n;
    // 一般使用线段树，都喜欢从下标1开始，所以我们在处理数据时尽量让下标从1开始
    // b[]在下面的代码中有两个阶段的含义，目前的含义是a[i]的备份，因为一会a[]由小到大排序后，原始数组就丢失了位置信息就不见了，需要b备份出来
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];

    // ① 原始数组由小到大排序
    sort(a + 1, a + n + 1);

    // ② 离散化，遍历原始数组b[i],找出它的排名，即b[2]=3表示第2个输入的是排名第3的
    for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + n + 1, b[i]) - a;

    // 构建线段树
    build(1, 1, n); // n个数字

    // 边查边添加
    for (int i = 1; i <= n; i++) {
        modify(1, b[i], 1);           // 占据b[i]这个位置
        ans += query(1, b[i] + 1, n); // 出现的比我早，号还比我大的有多少个
    }

    // 输出
    printf("%lld\n", ans);
    return 0;
}
```

### 七、总结
- 树状数组讲究的是逐个下场，动态统计前缀和