树状数组

写在最前

树状数组算是我目前学过最优雅好写的数据结构了。

树状数组也被称为二进制索引树(Binary Indexed Tree,BIT)，是一种高效的数据结构，它可以实现 $O(\log n)$ 的单点修改和前缀和查询。

核心思想

当我们想实现单点修改和区间查询时，肯定会有人想到用一个数组来维护若干个小区间的和，使得修改和查询的复杂度都不会那么高。

树状数组便是巧妙的运用了二进制来实现这一想法。

现在我们存储每一个位置前面 lowbit 位的和，也就是是说 $c_i=\sum_{j=i-lowbit(i)+1}^ia[j]$，比如 $i=6$，那么我们可以先将 6 转化为二进制 $(0110)_2$，显然 $c[6]=a[5]+a[6]$。

实现

查询

这里偷借一下老师的图（（（（

不难发现长得确实很像树如果现在要求前 $i$ 项的和，那么就可以通过每次减去 $lowbit(i)$ 得到的 $c_i$ 求和，具体来说就是 $sum[i]=c[i]+sum[i-lowbit[i]]$。

还是拿 6 举例，先化成二进制 $(0110)_2$。

  • $lowbit((0110)_2)=(0010)_2$，即 $lowbit(6)=2$
  • $(0110)_2-(0010)_2=(0100)_2$，即 $6-2=4$
  • $lowbit((0100)_2)=(0100)_2$，即 $lowbit(4)=4$
  • $(0100)_2-(0100)_2=(0000)_2$，即 $4-4=0$

所以 $c[6]=c[4]+c[2]$。

代码：

1
2
3
4
5
6
7
8
9
10
long long query(long long x)
{
    long long sum=0;
    while(x)
    {
        sum+=c[x];
        x-=(x&-x);
    }
    return sum;
}

修改

查询是从上往下退，修改也同理，从下往上爬就行了，不难发现，$i$ 的父节点即为 $i+lowbit(i)$。

代码：

1
2
3
4
5
6
7
8
void update(long long x,long long v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=(x&-x);
    }
}

不过这样实在是太屎山了，不妨把他封装起来：

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
class BIT
{
    long long c[N];
    long long prefix(long long x)
    {
        long long sum=0;
        while(x)
        {
            sum+=c[x];
            x-=(x&-x);
        }
        return sum;
    }
public:
    void update(long long x,long long v)
    {
        while(x<=n)
        {
            c[x]+=v;
            x+=(x&-x);
        }
    }
    long long query(long long l,long long r)
    {
        return prefix(r)-prefix(l-1);
    }
}
...
BIT c;//定义
c.update(i,x)//第 I 位加 x
c.query(l,r)//查询 l~r 的和

进阶

区间修改单点查询

结合单点修改区间查询，不难想到差分，我们只需要对差分数组做树状数组，这样需要区间修改的话只需要单点修改差分数组的两端，单点修改的话需要修改一整个区间。

1
2
c.update(l,x);c.update(r+1,-x);//l~r 加 x
c.query(1,x)//查询第 x 位

区间修改区间查询

先鸽着，有时间再来写实际是我钛菜了（（