树状数组

:::tip 今天想学一学树状树了，老是看见别人在说可以用树状数组来解题，但是因为不知道是个什么东西，就没有太过关注，今天不知道蹦到哪根经了，所以这篇就来了。 :::

# 树状数组解释与建立

树状数组一定和树、数组有着不可分割的关系，事实也确实是如此。由于图用mermaid画了好久都没画出来就不画了假如有这样的一个数组primary[1…n]={1,2,3,4,5,6,7,8}; 用tree[1…n]来表示树状数组，则他们之间有着以下的关系：

1
2
3
4
5
6
7
8


tree[1]=primary[1];
tree[2]=primary[1]+primary[2];
tree[3]=primary[3];
tree[4]=primary[1]+primary[2]+primary[3]+primary[4];
tree[5]=primary[5];
tree[6]=primary[5]+primary[6];
tree[7]=primary[7];
tree[8]=primary[1]+primary[2]+primary[3]+primary[4]+primary[5]+primary[6]+primary[7]+primary[8];

这样也许看的有点不是很明白

在数组的前面加上二进制编码

1
2
3
4
5
6
7
8


(0001)tree[1];
(0010)tree[2];
(0011)tree[3];
(0100)tree[4];
(0101)tree[5];
(0110)tree[6];
(0111)tree[7];
(1000)tree[8];

由这个二进制编码可以发现，末尾为1的就只等于当前数组，从低位往高位数，有k个连续的0，就说明需要加2^k个数,所以这就需要如何知道这些个连续的0呢，引入了lowbit函数

1
2
3
4


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

&是位运算，只有两个上下对应的二进制数都是1，结果才是1，否则为0.举几个例子吧第一个，假如说传入x=3。 3的二进制(011) -3的二进制(101) 结果为(001),那么就说明返回的是1

第二个，假如说传入x=4。 4的二进制(100) -4的二进制(100) 结果为(100),那么就说明返回的是4

那么这个函数可以干什么呢，可以判断这个primary[i]是否包含在tree[i]子集之中，如果被包含，那么就要把它加上，否则就要跳过。

接下来就把代码贴出来

 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


#include <iostream>
using namespace std;
int n;
int primary[500050];//原数组
int tree[500050];//树状数组
int lowbit(int x)//判断是否属于此棵子树的子节点
{
    return x & -x;
}
void change(int x, int p)
{
    while (x <= n)//添加一个节点，维护树状数组
    {
        tree[x] += p;//如果属于它的子节点就相加
        x += lowbit(x);//跳过与选择
    }
    return;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> primary[i];//输入一个数组的值
        change(i, primary[i]);//找它的根节点
    }
    for (int i = 1; i <= n; i++)//输出
    {
        cout << tree[i] << ' ';
    }
    return 0;
}

这个就是一个最简单的树状数组的建立过程了，完全是建立。

# 树状数组可以干什么

树状数组的时间效率非常的高，时间复杂度是nlogn，对于以下几种题型，优化的效果都很明显，高性能专用。

# 区间求和

 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


#include <iostream>
using namespace std;
int n,m;//n代表有几个元素，m代表有几组求和区间
int primary[500050];//原数组
int tree[500050];//树状数组
int lowbit(int x)//判断是否属于此棵子树的子节点
{
    return x & -x;
}
void change(int x, int p)
{
    while (x <= n)//添加一个节点，维护树状数组
    {
        tree[x] += p;//如果属于它的子节点就相加
        x += lowbit(x);//跳过与选择
    }
    return;
}
int sum(int k)//求k之前的和
{
    int ans = 0;
    while (k > 0)
    {
        ans += tree[k];
        k -= lowbit(k);
    }
    return ans;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> primary[i];//输入一个数组的值
        change(i, primary[i]);//找它的根节点
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin >> l >> r;
        cout << sum(r)-sum(l-1) << endl;//这为什么要减1，自己可以试试
    }
    return 0;
}

# 更新中间某一个值再求区间和

这种类型的题对应洛谷的P3374题

至于如何更新某一位置的值，可以使用上面的change函数，因为建造数组的时候，就是用这个函数一点点添加的，所以更改我们仍可以使用它。 x对应所在的位置，p对应所要增加或者减少的值。

# 求逆序数

没想到，树状数组也可以进行求逆序数，思想是这样的，把数组的值当作树状数组的下标，然后改变此下标值的大小为1(初始化所有数组的值都为0)，每次只需要判断此位置之前是否有比自己小的数，然后与添加了几个数(即i)相减，就可以求出这个数前面有几个比它大的。

 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


#include <iostream>
using namespace std;
int n, m;            //n代表有几个元素，m代表有几组求和区间
int primary[500050]; //原数组
int tree[500050];    //树状数组
int lowbit(int x)    //判断是否属于此棵子树的子节点
{
    return x & -x;
}
void change(int x, int p)
{
    while (x <= n) //添加一个节点，维护树状数组
    {
        tree[x] += p;   //如果属于它的子节点就相加
        x += lowbit(x); //跳过与选择
    }
    return;
}
int sum(int k) //求k之前的和
{
    int ans = 0;
    while (k > 0)
    {
        ans += tree[k];
        k -= lowbit(k);
    }
    return ans;
}
int main()
{
    int ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;//输入一个值
        change(a, 1);将所对应的位置改变为1
        ans += i - sum(a);//逆序数求和
    }
    cout << ans;
    return 0;
}