首页 > 代码库 > 树状数组入门

树状数组入门


传送门:https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/#introduction

下面对树状数组进行一些分析:

inline int Lowbit(int x)
{
return x&(-x);
}

void Update(int x, int c)
{
int i;
for (i = x; i < maxn; i += Lowbit(i))
tree[i] += c;
}

int Getsum(int x)
{
int i;
int temp=0;
for (i = x; i >= 1; i -= Lowbit(i))
temp += tree[i];
return temp;
}

现在对三个函数进行下分析:

Lowbit(x),是求出 2^p(其中 p 为 x 的二进制表示中最右边的那个 1 的位置),如 6 的二进制表示为 110,最右边的 1 为 1,故 Lowbit(6) = 2^1 = 2。

Update(x, c),是使 x 这点的值改变 c,如果是一般数组改变的就是 x自己这点,但是树状数组中要把(x, x+Lowbit(x), x+Lowbit(x+Lowbit(x))),…)这条路径的点都要改变 c,这样做是为了后面能够高效地求和。

Getsum(x), 是求的(1, …x-Lowbit(x-Lowbit(x))), x-Lowbit(x), x)这条路径的点的和,换句话说就相当于求一般数组 a[1]到 a[x]的和。

树状数组的最基本功能就是求比某点 x 小的点的个数(这里的比较是抽象的概念,可以使数的大小,坐标的大小,质量的大小等)。

比如给定个数组 a[5] = {2, 5, 3, 4, 1},求 b[i] = 位置 i 左边小于等于 a[i]的数的个数.如 b[5] = {0, 1, 1, 2, 0},这是最正统的树状数组的应用,直接遍历遍数组,每个位置先求出 Getsum(a[i]),然后再修改树状数组Update(a[i], 1)即可。当数的范围比较大时需要进行离散化,即先排个序,再重新编号。如 a[] = {10000000, 10, 2000, 20, 300},那么离散化后 a[] = {5, 1, 4, 2, 3}。

但我们想个问题,如果要求 b[i] = 位置 i 左边大于等于 a[i]的数的个数呢?当然我们可以离散化时倒过来编号,但有没有更直接的方法呢?答案是有。几乎所有教程上树状数组的三个函数都是那 样写的,但我们可以想想问啥修改就是 x 不断增加,求和就是 x 不断减少,我们是否可以反过来呢,答案是肯定的。

void Update(int x, int c)
{
int i;
for (i = x; i >= 1; i -= Lowbit(i))
{
tree[i] += c;
}
}

int Getsum(int x)
{
int i;
int temp(0);
for (i = x; i < maxn; i += Lowbit(i))
{
temp += tree[i];
}
return temp;
}
我们只是将两个函数中的循环语句调换了下,现在每次要修改点x的值,就要修改(1, …x-Lowbit(x-Lowbit(x))), x-Lowbit(x), x)路径,而求和就变成求(x, x+Lowbit(x), x+Lowbit(x+Lowbit(x))),…)这条路径的点。而这不正好就是大于等于 x 的点的求和吗?

所以我们既可以修改 x 增大的路,求和 x 减小的路;也可以修改 x 减小的路,求和 x 增大的路,根据题目的需要来决定用哪种。

注意:都是比较左边。如果需要比较右边只需要逆向输入。

树状数组入门