树状数组（Fenwick Tree），这次EC Final遇到过的，英文也记一下，也来学一下，刚好半夜刷题刷到了树状数组可以解决的题目！

简介

树状数组和线段树具有相似的功能，但他俩毕竟还有一些区别：树状数组能有的操作，线段树一定有；线段树有的操作，树状数组不一定有。但是树状数组的代码要比线段树短，思维更清晰，速度也更快，在解决一些单点修改的问题时，树状数组是不二之选。

原理

下面这张图展示了树状数组的工作原理：

这个结构和线段树有些类似：用一个大节点表示一些小节点的信息，进行查询的时候只需要查询一些大节点而不是所有的小节点。

最上面的八个方块就代表数组 $a$。

他们下面的参差不齐的剩下的方块就代表数组 $a$ 的上级——$c$ 数组。

从图中可以看出：
$c_2$ 管理的是 $a_1$,$a_2$；
$c_4$ 管理的是 $a_1$,$a_2$,$a_3$,$a_4$；
$c_6$ 管理的是 $a_5$,$a_6$；$c_8$ 则管理全部 $8$ 个数。

如果要计算数组 $a$ 的区间和，比如说要算 $a_{51}$~$a_{91}$ 的区间和，可以采用类似倍增的思想：

从 $91$ 开始往前跳，发现 $c_n$（$n$ 我也不确定是多少，算起来太麻烦，就意思一下）只管 $a_{91}$ 这个点，那么你就会找 $a_{90}$，发现 $c_{n - 1}$ 管的是 $a_{90}$&$a_{89}$；那么你就会直接跳到 $a_{88}$，$c_{n - 2}$ 就会管 $a_{81}$~$a_{88}$ 这些数，下次查询从 $a_{80}$ 往前找，以此类推。

用法及操作

那么问题来了，怎么知道 $c_i$ 管理的数组 $a$ 中的哪个区间呢？
这时，我们引入一个函数——lowbit：

1
2
3
4
5
6
7
8
9
// C++ Version
int lowbit(int x) {
  // x 的二进制表示中，最低位的 1 的位置。
  // lowbit(0b10110000) == 0b00010000
  //          ~~~^~~~~
  // lowbit(0b11100100) == 0b00000100
  //          ~~~~~^~~
  return x & -x;
}

注释说明了 lowbit 的意思，对于 $x=88$：$88_{(10)}=1011000_{(2)}$
发现第一个 $1$ 以及他后面的 $0$ 组成的二进制是 $1000$
$1000_{(2)} = 8_{(10)}$
$1000$ 对应的十进制是 $8$，所以 $c_{88}$ 一共管理 $8$ 个 $a$ 数组中的元素。

在常见的计算机中，有符号数采用补码表示。在补码表示下，数 x 的相反数 -x = ~x + 1。

使用 lowbit 函数，我们可以实现很多操作，例如单点修改，将 $a_x$ 加上 $k$，只需要更新 $a_x$ 的所有上级：

1
2
3
4
5
6
7
// C++ Version
void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

前缀求和：

1
2
3
4
5
6
7
8
9
// C++ Version
int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x >= 1) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

区间加 & 区间求和

若维护序列 $a$ 的差分数组 $b$，此时我们对 $a$ 的一个前缀 $r$ 求和，即 $\sum_{i=1}^{r} a_i$，由差分数组定义得 $a_i=\sum_{j=1}^i b_j$

进行推导

$$
\begin{aligned}
&\sum_{i=1}^{r} a_i\=&\sum_{i=1}^r\sum_{j=1}^i b_j\=&\sum_{i=1}^r b_i\times(r-i+1)
\=&\sum_{i=1}^r b_i\times (r+1)-\sum_{i=1}^r b_i\times i
\end{aligned}
$$

区间和可以用两个前缀和相减得到，因此只需要用两个树状数组分别维护 $\sum b_i$ 和 $\sum i \times b_i$，就能实现区间求和。

代码如下

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
// C++ Version
int t1[MAXN], t2[MAXN], n;

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

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}

Tricks

$O(n)$ 建树：

每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新自己的直接父亲。

1
2
3
4
5
6
7
8
9
// C++ Version
// O(n)建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

区间加法&单点查询

只要把我们原来维护的数组进行差分即可。这样的话我们原来 get_sum(x) 的操作就会变成查询 x 点的值 ，因为我们维护的是差分数组，所以在区间加法的时候我们只需要对端点修改即可，复杂度都是 $O(log_2n)$。

以上大部分内容来自 OI WIKI。

例题：CF1679C

题目描述

题目分析

这题题面比较长，但是出的确实比较好。大概就是说给你一张 $n \times n$ 的棋盘，然后给你 3 种类型的操作。

  1. 在 $(x,y)$ 中放入一辆车，保证原位置没车
  2. 在 $(x,y)$ 中取出一辆车 ，保证原位置有车
  3. 选取一块矩形，由左上角端点坐标和右下角端点坐标描述。让你判断这个矩形区域内是否都在车的攻击范围内。

那么你在没有看到 $n\times n$ 有范围限制就应该能想到了，这题肯定不能存储棋盘，而要描述车的位置。1，2操作我们可以堪称是单点修改，3操作可以看成是区间查询。那么想到这两点就能很好的想到树状数组了。我们把棋盘横竖分离，横坐标建一棵树状数组，纵坐标也建一棵树状数组，那么在插入 $(x,y)$ 的时候我们就可以对横坐标的 $x$ 位置进行单点修改，纵坐标的 $y$ 进行单点修改。其实哪种叫法无所谓，你只要对应上就可以了，不必纠结横纵坐标。那么再仔细解读一下它的第三个要求，判断是否能被车都撞到，那我们很容易想到，横坐标范围都有车或者纵坐标范围都有车，那这个区域都能被车撞到，就可以了，这个区间查询我们查横纵坐标，有一方满足即可。但是需要注意，我们要做一点修改，因为假如一行上面有两辆车，而上一行恰好没有车，那么这两行显然上面那一行不能被撞到，但是因为这两行区间查询得到 $2$ 我们可能误认为它能撞到这两行，那么这显然不符合逻辑。于是我们可以另外开一个数组记录这一行（列）上面车的数量，给树状数组增加的时候我只用保证这一行（列）之前没有车就行了，同样给树状数组减少的时候我们要确保这一行（列）都没车了，才能减少。这样我们就能愉快地 AC 这题了。

这个题目出的是真的好！

标程

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
int n,m;
int c[maxn],d[maxn];

int lowbit(int x){
    return x&-x;
}

void add(int x,int val,int *c){
    
    while(x<=n){
        //printf("%d %d\n",x,val);
        c[x]+=val;
        x+=lowbit(x);
    }
}

int get_sum(int x,int *c){
    int ans=0;
    while(x>=1){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int cnt1[maxn],cnt2[maxn];

void solve(){
    int q;
    scanf("%d%d",&n,&q);
    while(q--){
        int t,x,y,x1,y1;
        scanf("%d",&t);
        if(t==1){
            scanf("%d%d",&x,&y);
            cnt1[x]++;
            cnt2[y]++;
            if(cnt1[x]==1)add(x,1,c);
            if(cnt2[y]==1)add(y,1,d);
        }
        else if(t==2){
            scanf("%d%d",&x,&y);
            cnt1[x]--;
            cnt2[y]--;
            if(!cnt1[x])add(x,-1,c);
            if(!cnt2[y])add(y,-1,d);
        }
        else{
            scanf("%d%d%d%d",&x,&y,&x1,&y1);
            if((get_sum(x1,c)-get_sum(x-1,c))==(x1-x+1)||(get_sum(y1,d)-get_sum(y-1,d))==(y1-y+1)){
                puts("YES");
            }
            else{
                puts("NO");
            }
        }
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    //cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

小结

树状数组很后悔没有很早学起来，因为它真的比线段树简单太多了，可惜我是先会的线段树，所以导致就没兴趣学树状数组，不过没事，现在会了也是不迟的！