树状数组:从单点更新区间查询到区间更新单点查询

树状数组(Binary Indexed Tree, BIT)是一种可以实现单点更新,区间查询的数据结构,每次操作复杂度为 $O(logn)$。

它的实现主要包括两个函数:

  • $sum(i)$ 表示 $i$ 所在位置的前缀和(即 $a_1+a_2+…+a_i$,下标从 $1$ 开始)
  • $add(i, x)$ 表示给 $a_i$ 加上 $x$

这里不详细讲实现的原理,有需要的请自行百度或Google。

BIT的求和

计算前 $i$ 项的和需要从 $i$ 开始,不断把当前位置 $i$ 的值加到结果中,并从 $i$ 中减去 $i$ 的二进制最低非 $0$ 位对应的幂,直到 $i$ 变成 $0$ 为止。 $i$ 的二进制的最后一个 $1$ 可以通过 $i$ & $-i$得到。

1
2
3
4
5
6
7
8
9
10
int sum(int i)
{

int s = 0;
while( i > 0 )
{
s += bit[i];
i -= i & -i;
}
return s;
}


BIT的值的更新

使第 $i$ 项的值增加 $x$ 需要从 $i$ 开始,不断把当前位置 $i$ 的值增加 $x$,并把 $i$ 的二进制最低非 $0$ 位对应的幂加到 $i$ 上。

1
2
3
4
5
6
7
8
void add(int i, int x)
{

while( i <= n )
{
bit[i] += x;
i += i & -i;
}
}


转化:从单点更新区间查询转化为区间更新单点查询

Ps: 一般来讲,区间总是包含单点的,也就是可以 区间更新/查询 一定也可以 单点更新/查询,反过来却未必。

上面讲的可以实现单点更新区间查询,那如果我们需要区间更新单点查询呢?只能写线段树?

不是的。我们可以这样进行区间 $[L,R]$ 的更新:

add(L, x);
add(R + 1, -x);

add函数不需要改变。
为什么这样就可以呢?考虑 $sum(i)$ 为位置 $i$ 的前缀和,若我们将其当成 $a_i$ 位置的值,那之前的更新就是成功的。比如说一开始要使 $[1,5]$ 的值增加3,按我们的做法,便只有两步操作 $add(1,2)$ 和 $add(6,-2)$。这样当你查询 $a_3$ 的值时,$sum(3)$ 就会计算到之前位置 $1$ 增加的 $2$。就相当于 $3$ 这个位置增加了 $2$。

可能有些人会疑惑 $sum(i)$ 的前缀和部分呢?很简单,我们只要在初始化赋值时这样操作就可以了:

add(i, x);
add(i + 1, -x);

单点更新同理。

至于说区间更新区间查询,虽然BIT也可以做,但感觉还不如直接线段树来得方便。这里就不细讲了,有兴趣的可以看下《挑战程序设计竞赛》这本书,里面有讲解这种做法。

BIT区间更新单点查询举个栗子:URAL 2030

以上。

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!