TIP

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

# 树状数组解释与建立

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

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];

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

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

(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函数

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]子集之中,如果被包含,那么就要把它加上,否则就要跳过。

接下来就把代码贴出来

#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,对于以下几种题型,优化的效果都很明显,高性能专用。

# 区间求和

#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)相减,就可以求出这个数前面有几个比它大的。

#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;
}