姓名： 郑皓仁
赛道： 提高组
类型： 算法技能
树状数组（BIT）
关键词： 树状数组, BIT, lowbit
什么是树状数组
树状数组是一种码量小，常数小，支持单点修改和区间查询的数据结构。
树状数组维护的信息和运算需要满足结合律并且可差分
注意gcd和max操作虽然满足结合律，但不可差分，因此不能使用树状数组维护
其实，树状数组能做的，线段树都能做，线段树能做的，树状数组不一定能做，但线段树码量大，常数大，不像树状数组，码量小，常数小, ~适合我这种懒人使用~。因此还是要学的，毕竟谁都不想再考场上手打一个线段树。
进过一些操作后树状数组也可以支持区间查询和单点修改，这个我们待会再说。
如何实现
引入
让我们先来看一个问题：
给定一个序列，满足以下操作
- 将某一个数加上一个值
- 查询 l 到 r 的和
假设你还没学过线段树和树状数组，你会怎么做这道题。
显然有两种方法
方法1：直接模拟，修改 O(1) ，查询 O(n)
方法2：前缀和，修改 O(n) ，查询 O(1)
然而，如果操作次数很多序列又很长的话上面的做法就显得有些无力了，这时我们就需要使用树状数组来解决这个问题。
树状数组计算 a_1+a_2+a_3+a_4+...+a_n 是把它们拆成不超过 \log n 段进行计算，这样我们只需要合并 \log n 段区间就能够计算出结果，相比于暴力效率有很大的提高。下面是一张简图，生动的展示了树状数组的工作原理。
最下面的八个方块表示原始数组，上面的方块就是c数组，用来存放某一段区间的和, 这些信息是已知的，我们可以把前缀和拆成这些小区间来计算。
从图中可以看出， c[i] 存的是以 i 为右端点的一段区间的和，让我们先不管左端点，来感受一下树状数组是如何查询的。
例如我们要查询 [1,7] 的区间和。就会从 c[7] 开始跳，先将答案加上 c[7] ，发现 c[7] 计算的是 [7, 7] 的和，于是我们跳到 c[6] ，发现 c[6] 算的是 [5,6] 的和，所以我们跳到 c[4] ，并将答案加上 c[6] 。 c[4] 算的是 [1,4] 的和，我们将答案加上 c[4] ，但此时前面已经没有可跳了，所以过程结束，返回答案。
如果我们要查询 [4, 7] 的和怎么办呢，我们可以利用前缀和的思想，用 [1,7] 的和减去 [1,3] 的和就好了。
区间大小
现在我们来考虑左端点在哪里。
在树状数组中，我们规定 c_x 的存的是 [x-\operatorname{lowbit}(x)+1, x] 的和。 \operatorname{lowbit}(x) 指的是 x 这个数在二进制下最低位的1的位权。
我们要如何计算 \operatorname{lowbit}(x) 呢。根据位运算知识得， \operatorname{lowbit}(x) = x\ \& -x ，有人肯定要问，为什么？ 下面是一段摘自oiwiki的解释，可能可以帮助理解。
将 x 的二进制所有位全部取反，再加 1，就可以得到 -x 的二进制编码。例如，6 的二进制编码是 110，全部取反后得到 001，加 1 得到 010。
设原先 x 的二进制编码是 (…)10…00，全部取反后得到 […]01…11，加 1 后得到 […]10…00，也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1 是 x 最低位的 1。
(…) 和 […] 中省略号的每一位分别相反，所以 x & -x = (…)10…00 & […]10…00 = 10…00，得到的结果就是 \operatorname{lowbit} 。
代码实现：
int lowbit(int x){
return x & -x;
}
区间查询
回顾一下刚才举的例子，不难想出查询前缀和的方法，我们写出计算 [1, x] 的和的过程。
- 将 ans 加上 c_x
- x 减去 \operatorname{lowbit}(x)
- 判断 x 是否为 0 ，不是就回到第1步，否则返回 ans
代码实现：
int sum(int x){
int res = 0;
while(x){
res += c[x];
x -= lowbit(x);
}
return res;
}
那么我们可以写出查询 [l, r] 区间和的代码
int query(int l, int r){
return sum(r) - sum(l-1);
}
区间查询部分完结。
单点修改
修改一个值其实只需要把管辖了 a_x 的 c_y 找到并修改即可，那我们怎么找到管辖了 a_x 的 c_y 呢？
显而易见的， c_x 管辖了 a_x 。在之前的那副简图中可以看出 c[x] 被 c[x+\operatorname{lowbit}(x)] 包含。
于是我们就有了一种找的方法，假设要把 a_x 加上 y ， 下面给出过程。
- 将 c_x 加上 a_x 。
- x 加上 \operatorname{lowbit}(x)
- 如果 x 大于 n 那么退出，否则回到第1步。
代码如下：
void modify(int x, int y){
while(x <= n){
c[x] += y;
x += lowbit(x);
}
}
建树
可以直接转换为 n 次单点修改。
代码如下：
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
modify(i, x);
}
完整代码
#include<bits/stdc++.h>
using namespace std;
int n, m, c[1000010];
int lowbit(int x){
return x & (-x);
}
void modify(int x, int y){
while(x <= n){
c[x] += y;
x += lowbit(x);
}
}
int sum(int x){
int res = 0;
while(x >= 1){
res += c[x];
x -= lowbit(x);
}
return res;
}
int query(int l, int r){
return sum(r) - sum(l-1);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
modify(i, x);
}
for(int i = 1; i <= m; i++){
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if(opt == 1){
modify(x, y);
}else{
printf("%d\n", query(x, y));
}
}
return 0;
}
好了，你已经学会了基础的树状数组，接着我们来学习如何让树状数组支持区间修改单点查询
区间修改单点查询
题目：【模板】树状数组 2
我们发现如果树状数组维护的是原本的数组则无法实现，考虑维护差分数组。
我们知道在如果要将 [l, r] 的所有数加上 x 的话，只需要在差分数组的第 l 位加上 $x$，再在第 r+1 位减去 x 即可。
而查询第 x 个数是多少其实就是计算差分数组前 x 个数的和。这两个操作树状数组都可以实现，于是我们就做完了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n, m, a[1000010], b[1000010], c[1000010];
int lowbit(int x){
return x & (-x);
}
void modify(int x, int y){
for(int i = x; i <= n; i += lowbit(i)){
c[i] += y;
}
return ;
}
int query(int x){
int res = 0;
for(int i = x; i; i -= lowbit(i)){
res += c[i];
}
return res;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
b[i] = a[i] - a[i-1];
modify(i, b[i]);
}
while(m--){
int opt;
scanf("%d", &opt);
if(opt == 1){
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
modify(l, x);
modify(r+1, -x);
}else if(opt == 2){
int p;
scanf("%d", &p);
printf("%d\n", query(p));
}
}
return 0;
}
好了，现在你已经学会了基本的树状数组，来做几道例题吧
例题
例题1：[CQOI2006] 简单题
这是一道树状数组板子题，只需要把区间修改单点查询的加法改为异或就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n, m, c[100001];
int lowbit(int x){
return x & (-x);
}
void add(int x){
for(int i = x; i <= n; i += lowbit(i)){
c[i] ^= 1;
}
}
int sum(int x){
int res = 0;
for(int i = x; i; i -= lowbit(i)){
res ^= c[i];
}
return res;
}
int main(){
scanf("%d%d", &n, &m);
while(m--){
int opt, l, r;
scanf("%d%d", &opt, &l);
if(opt == 1){
scanf("%d", &r);
add(l);
add(r+1);
}else{
printf("%d\n", sum(l));
}
}
return 0;
}
例题2：HH的项链
首先，如果一个贝壳反复出现，那我们只要关注它出现的某一个位置而忽略其他位置，显而易见的，我们可以关注最右边的位置，因为好更新。
既然关注右边的贝壳，那么我们就要从左到右的处理数组，注意到这题不强制在线，于是我们可以离线后按照右端点排序，这样保证了右边的数是按顺序更新的。
查询的时候利用前缀和思想即可。
下面引入一个数组 vis 。 vis_i 表示第 i 种贝壳在目前询问的区间内最后出现的位置。还有一个名叫 last 的变量，意思是还没修改区间的左端点，每次更新从它开始。
我们写出修改部分的代码：
int last = 1;
for(int i = 1; i <= m; i++){
for(int j = last; j <= q[i].r; j++){
if(vis[a[j]]) modify(vis[a[j]], -1);//如果之前有这个数就先把它删掉
modify(j, 1);//用新的位置代替
vis[a[j]] = j;//修改vis数组
}
last = q[i].r+1;//更新last
ans[q[i].id] = query(q[i].r) - query(q[i].l-1);
}
总代码，可以配合理解：
#include<bits/stdc++.h>
using namespace std;
namespace qwq{
inline int read(){
int n = 0;
int f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
n = (n << 3) + (n << 1) + (c ^ 48);
c = getchar();
}
return n * f;
}
inline void Write(int x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9) Write(x / 10);
putchar((x % 10) ^ 48);
return;
}
inline void write(int x, char c){
Write(x);
putchar(c);
}
}
using namespace qwq;
struct node{
int l, r, id;
bool operator < (const node &A){
return r < A.r;
}
} q[1000010];
int tree[1000010], n, m, a[1000010], vis[1000010], ans[1000010];
int lowbit(int x){
return x & (-x);
}
void modify(int x, int y){
while(x <= n){
tree[x] += y;
x += lowbit(x);
}
}
int query(int x){
int res = 0;
while(x){
res += tree[x];
x -= lowbit(x);
}
return res;
}
int main(){
n = read();
for(int i = 1; i <= n; i++){
a[i] = read();
}
m = read();
for(int i = 1; i <= m; i++){
q[i].l = read(), q[i].r = read(), q[i].id = i;
}
sort(q+1, q+m+1);
int last = 1;
for(int i = 1; i <= m; i++){
for(int j = last; j <= q[i].r; j++){
if(vis[a[j]]) modify(vis[a[j]], -1);
modify(j, 1);
vis[a[j]] = j;
}
last = q[i].r+1;
ans[q[i].id] = query(q[i].r) - query(q[i].l-1);
}
for(int i = 1; i <= m; i++){
write(ans[i], '\n');
}
return 0;
}
这道题还有一个莫队做法，感兴趣的读者可自行了解。
结语
上面就是我的总结和笔记，这里其实还有很多技巧没有讲到，例如扫描线等，之后可能会补充。还有树状数组虽然代码短，但适用范围小，线段树还是要学的。让我们一起，向着神犇的路进发。