[算法]浅谈树状数组
wangyibo201026
·
·
个人记录
前置知识
-
了解二进制以及性质。
-
了解计算机中的原码，反码，补码。
这些是学会树状数组的必备功，如果不会可以上网搜一下（反正不会耽误你多少时间）。
树状数组是什么？
以上是它的简介。
树状数组的思想
树状数组（Binary Indexed Tree），是一种数据结构，我们还是通过一个题目来了解它：P3374。
我们又来想暴力啦！
-
暴力，时间复杂度 O(N^2)。
-
前缀和，时间复杂度 O(N^2)。
-
线段树，可以过但代码太长。
现在假设你不会写线段树，那么我们就需要树状数组这种数据结构。
注意，下面的部分建议读者反复观看。
树状数组的主要思想就是二进制拆分，我们来看看是怎么个拆法。
首先假设我们的序列为
13
1 0 2 1 2 3 0 3 0 5 3 2 1
首先我们将 13，也就是所谓的 n 进行转二进制，得 1101，我们发现这个二进制数里有三个 1，也就是说 13 = 2^3 + 2^2 + 2^0，这里利用倍增得思想，从大到小排，听不懂也没关系。
所以我们可以将整个序列 13 个数分成以下几个部分：
13
1 0 2 1 2 3 0 3 | 0 5 3 2 | 1
| 为分隔符，所以我们发现每个部分得长度对应这这些二进制 1 的数值，由于一个数的二进制拆分是唯一的，所以这些部分也都是唯一的。我们可以用 tree 数组来存放每个部分的数值和，现在我们规定以下 tree 的存储方式：
为什么这么定义呢？我们可以发现，$8$ 正好就是 $2^3$，$12$ 正好就是 $2^3 + 2^2$，而 $13$ 又正好就是 $2^3 + 2^2 + 2^0$。我们发现，每个部分记录数值和的 $tree$ 下标都是不断以 $1$ 的数值叠加的。
### 最初的最初（$\text{lowbit}$）
我们该怎样计算这些 $tree$ 的下标呢？这里我们就需要用到函数 $\text{lowbit}$，意思是最低位。它表示的是一个数的二进制数的最低位的 $1$ 以及跟后面的 $0$ 所组成的数。就比如说 $13$ 的二进制数 $1101$ 的 $\text{lowbit}$ 就是二进制数 $1$，也就是十进制数 $1$。
那么我们发现，第三个部分 $tree$ 的下标是 $13$，也就是 $n$，而第二个部分 $tree$ 的下标就是 $13 - \text{lowbit(13)}$，也就是 $12$，继续下去，第一个部分 $tree$ 的下标就是 $12 - \text{lowbit(12)}$，也就是 $8$!
实际上，这样的事情并不是巧合，而是从 $tree$ 的下标的本身规律来定义的 $\text{lowbit}$。
现在我们考虑 $\text{lowbit}$ 如何计算，难道就真的要二进制拆分吗？其实不需要，我们发现，一个数的二进制与这个二进制数的取反加 $1$ 相互进行 $\&$ 操作就正好是这个数的 $\text{lowbit}$！具体原因可以上网搜，又由于这个二进制数的取反加 $1$ 正是这个数的补码（$x$ 的补码等于 $-x$），所以 $\text{lowbit}(x) = x \& -x$！
### 关于一些关系问题
比如说要查询 $1$ ~ $13$，那么最初加上 $tree_{13}$ 之后又要加上什么呢？我们应该是要加上 $tree_8$，如果你仔细思考的话，就知道 $8 = 13 - \text{lowbit}(13)$，那么这个部分的后面那个部分的下标就是 $x + \text{lowbit}(x)$，前面部分的下标就是 $x - \text{lowbit}(x)$。
### 更新（$\text{update}$）
由于更改一个点只会讲后面部分的节点前缀和给更改，所以应该是不断 $ + \text{lowbit}(x)$。
```cpp
void update(int x, int val){
while(x <= n){
tree[x] += val;
x += lowbit(x);
}
}
```
### 查询（$\text{query}$）
```cpp
int query(int x){
int sum = 0;
while(x > 0){
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
```
### 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x & -x)
using namespace std;
const int N = 5e5 + 5;
int n, m;
int tree[N];
int query(int x){
int sum = 0;
while(x > 0){
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
void update(int x, int val){
while(x <= n){
tree[x] += val;
x += lowbit(x);
}
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
update(i, x);
}
while(m--){
int op;
cin >> op;
if(op == 1){
int x, k;
cin >> x >> k;
update(x, k);
}
else{
int x, y;
cin >> x >> y;
cout << query(y) - query(x - 1) << endl;
}
}
return 0;
}
```
## 树状数组可以解决什么问题？
树状数组擅长解决这两类问题：
1. 逆序对。
2. 二维偏序。
### 逆序对
这里有两种方法。
#### 1. 离散化
我们可以讲以权值建树状数组，然后将值进行 $+ 1$ 操作，然后直接前缀和一下就可以了
代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
struct Node{
int x;
int p;
}a[N];
int n, ans;
int d[N];
int vis[N];
int lowbit(int x){
return x & -x;
}
void update(int x, int c){
for(int i = x; i <= n; i += lowbit(i)){
d[i] += c;
}
}
int query(int x){
int sum = 0;
for(int i = x; i; i -= lowbit(i)){
sum += d[i];
}
return sum;
}
bool cmp(Node x, Node y){
if(x.x == y.x){
return x.p < y.p;
}
return x.x < y.x;
}
void Solve(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].x;
a[i].p = i;
}
sort(a + 1, a + 1 + n, cmp);
for(int i = 1; i <= n; i++){
vis[a[i].p] = i;
}
for(int i = 1; i <= n; i++){
update(vis[i], 1);
ans += (i - query(vis[i]));
}
cout << ans;
}
signed main(){
Solve();
return 0;
}
```
应该很简单。
#### 2. 排序
首先我们按照下标建树状数组，然后我们把 $a$ 排序（升序），每次查询前缀和，然后将本身 $ + 1$ 就行了。
~~代码没有~~