树状数组

树状数组是什么东西？

先戳维基百科树状数组条目

简单来说，树状数组就是一种可以大大降低维护一个数字序列的时间复杂度的数据结构。

树状数组的定义

树状数组的具体做法是这样的：
假设原始的数字序列为\(A_ {i}\),树状数组的序列为\(C_ {i}\)。
则有：

  • \(C_{1} = A_{1}\)
  • \(C_{2} = A_{1}+A_ {2}\)
  • \(C_{3} = A_{3}\)
  • \(C_{4} = A_{1}+A_{2}+A_{3}+A_{4}\)
  • \( \cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\)
  • \(C_{n} = A_{n-lowbit(n)+1}+ A_{n-lowbit(n)+2}+\cdots\cdots+A_{n}\)

然后看完这张经典的图之后，大概就可以明白树状数组是怎么回事了。

树状数组

lowbit是什么鬼？

这里不得不提一下lowbit()函数。
它返回的是：参数转为二进制后, 最后一个1的位置所代表的数值。
其实lowbit的意思就是最低位的意思，也就是参数的二进制形式最低位的1所代表的数字。

lowbit()函数有三种具体的实现方法，用的都是位运算的知识。

  • lowbit1(x) = x&(x^(x-1))
  • lowbit2(x) = x&(~x+1)
  • lowbit3(x) = x&(-x)

优点和缺点

为什么要这么做呢？用lowbit有什么好处呢？

最大的优点当然是维护一个序列啦，时间复杂度好低的, 只有\(log_ {2}(n)\)哦！
还有一个优点就是实现起来灰常简单，简单到爆，这是一个小巧。

如果我们要知道某个数字之前所有数字的和，可以这么做：

\[\sum _{i=1} ^{n}{A_i}=C _{n} + C _{n-lowbit(n)} + C _{n-lowbit(n)-lowbit(n-lowbit(n))} + \cdots\cdots\cdots \]

要知道一个区间(x,y)的数字的和，用\[\sum _{i=1} ^{y}{A_i}- \sum _{i=1} ^{x-1}{A_i}\]即可求出。

要修改某个位置(x)的值，需要修改\[C _{x}, C _{x+lowbit(x)}, C _{x+lowbit(x)+lowbit(x+lowbit(x))}, \cdots\cdots\cdots\cdots \]等一系列节点，时间复杂度也不会超过\(log _{2} (n)\)

那么树状数组有什么缺点呢？

当然是：应用范围太狭窄了！ 它只能维护序列前缀和有木有？

但是聪明的人类总能想到各种各样奇葩(机智)的用法。

树状数组的用途

C语言实现

lowbit函数

好吧，我喜欢用宏定义(昨天灵机一动写出来的)。

1
2
#define lowbit(o) ({int _=o; _&(~_+1);})
typedef long long LINT //再来个typedef方便使用

更新节点

1
2
3
4
5
6
7
8
9
10
11
12
/*
@bint  树状数组
@pos   需要更新的节点
@value 需要更新的值
@lmt   树状数组的最大范围
*/
void add(LINT *bint, int pos, int value, int lmt){
    while(pos > 0 && pos < lmt){
        bint[pos] += value;
        pos += lowbit(pos);
    }    
}

求和函数

1
2
3
4
5
6
7
8
LINT sum(LINT *bint, int pos, int lmt){
    LINT ans = 0;
    while(pos > 0 && pos < lmt){
        ans += bint[pos];
        pos -= lowbit(pos);
    }
    return ans;
}

三种神奇的用法

修改点值，求区间和

修改：把pos位置的值加上或者减去一个值delta。

1
add(bint, pos, delta, n+1);

询问：求区间\((left,right)\)的区间和。

1
sum(bint, left, n+1)-sum(bint, right, n+1);

修改区间，求点值

需要更改一下策略：用树状数组维护原始数组的前缀和

修改：把区间\((left,right)\)的每个位置的值都加上或者减去一个值delta。

1
2
add(bint, left, delta, n+1);
add(bint, right+1, -delta, n+1);

询问：求pos位置的值。

1
sum(bint, pos, n+1);

修改区间，求区间和

待补充。

强力扩展——二维树状数组

待补充。