【高级数据结构】树状数组

一、树状数组的介绍

1.思维导引

树状数组 $(B ina ry I n d e x e d T ree, B I T)$ 是利用数的二进制特征进行检索的一种树状的结构。

如何利用二分的思想高效地求前缀和?
如图 $4.7$ 所示, 以 $A$ $a_1,$ $a_2$ , $a_3$ … $a_8]$ 为例,将二叉树的结构画成树状。

这幅图是树状数组的核心,理解了它,就能明白树状数组的一切操作。

图 $4.7$ 圆圈中标记有数字的节点,存储的是称为树状数组的 $t ree []$ 。

一个节点上的 $t ree []$ 的值就是其树下的直连的子节点的和。

例如:
$tree[1]=a_1$
$tree[2]=tree[1]+a_2$
$tree[3]=a_3$
$tree[4]=tree[2]+tree[3]+a_4$
…
$treel[8]=tree[4]+tree[6]+tree[7]+a_8$

利用 $t ree []$ 可以高效地完成以下两个操作。

$(1)$ 查询,即求前缀和 $s u m$ 。

例如:
$s u m (8) = t ree [8]$ , $s u m (7) = t ree [7] + t ree 6] + t ree [4]$
$s u m (6) = t ree [6] + t ree [4]$

如图 $4.7$ 所示,下图中的虚线箭头是计算 $s u m (7)$ 的过程。

显然,计算复杂度为 $O (l o g 2 n)$ ,这样就达到了快速计算前缀和的目的。

$(2)$ 维护。

$t ree []$ 本身的维护也是高效的。当元素 $a$ 发生改变时,能以 $O(log_2n)$ 的高效率修改 $t ree []$ 的值。

例如,更新了 $a_3$ , ,那么只需要修改 $t ree [3], t ree [4] . t ree [8]$ ,即修改它和它上面的那些节点:父节点(后文指出, $x$ 的父节点是 $x + l o w bi t (x))$ 以及父节点的父节点。

有了方案,剩下的问题是如何快速计算出 $t ree []$ 。

观察查询和维护两个操作,发现(读者完全可以自己观察树状数组的原理图,根据二进制的特征得到以下结论):

$(1)$ 查询的过程是每次去掉二进制的最后的 $1$ 。例如,求 $s u m (7) = t ree [7] + t ree [6] + t ree [4]$ ,

步骤如下:

$1 、 7$ 的二进制是 $111$ ,去掉最后的 $1$ ,得 $110$ ,即 $t ree [6]$ ;
$2 、$ 去掉 $6$ 的二进制 $110$ 的最后一个1 $,$ 得 $100$ ,即 $t ree [4]$ ;
$3 、$ $4$ 的二进制是 $100$ ,去掉 $1$ 之后就没有了。

$(2)$ 维护的过程是每次在二进制的最后的 $1$ 上加 $1$ 。

例如,更新了 $a_3$ ,需要修改 $t ree [3] 、 t ree [4], t ree [8]$ 等

步骤如下:

$1 、$ $3$ 的二进制是 $11$ ,在最后的 $1$ 上加 $1$ 得 $100$ ,即 $4$ ,修改 $t ree [4]$ ;
$2 、$ $4$ 的二进制是 $100$ ,在最后的 $1$ 上加 $1$ ,得 $1000$ ,即 $8$ ,修改 $t ree [8]$ ;
$3 、$ 继续修改 $t ree [16]$ , $t ree [32]$ 等。

最后,树状数组归结到一个关键问题:如何找到一个数的二进制的最后一个 $1$ 。

2.神奇的 $l o w bi t (x)$

$lowbit(x)=x\&-x$ 功能是找到 $x$ 的二进制数的最后一个 $1$ 。
其原理是利用了负数的补码表示,补码是原码取反加 $1$ 。

例如, $x =6 =00000110_2$ , $x =x_补=11111010_2$

那么 $lowbit(x)=x\&(-x)=10_2=2$ 。

$l o w bi t (x)$ 的结果如表 $4.1$ 所示 $(x = 1 - 9)$
在这里插入图片描述

令 $m = l o w bi t (x), t ree [x]$ 的值是把 $a_x$ 。和它前面共 $m$ 个数相加的结果。如表 $4.1$ 所示。

例如, $l o w bi t (6) = 2$ ,有 $tree[6]=a_5+a_6$ .

$t ree []$ 是通过 $l o w bi t ()$ 计算出的树状数组,它能够以二分的复杂度存储一个数列的数据。
具体地, $t ree [x]$ 中存储的是区间 $[x — l o w bi t (x) + 1, r]$ 中每个数的和。

表 $4.1$ 可以画成图 $4.8$ 。

横条中的黑色部分表示 $t ree [x]$ ,它等于横条上元素相加的和。
在这里插入图片描述

二、树状数组的基本应用

1.单点修改+区间查询

这是最常规的树状数组模板，代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn =5e5 + 10;
const int maxm = 5e5 + 10;
#define int long long
int n,m;
int tree[maxn]; //树状数组
/* 树状数组 */
inline int lowbit(int x) { //神奇的lowbit函数！return x & (-x);
}
//单点修改
void add(int i,int x) {while (i <= n) {tree[i] += x;i += lowbit(i);}
}
//区间查询 返回1-i的和
int query(int i) {int res = 0;while (i > 0) {res += tree[i];i -= lowbit(i);}return res;
}
signed main() {ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {int x;cin >> x;add(i, x);}while (m--) {int op, x, y;cin >> op;if (op == 1) {cin >> x >> y;add(x, y);}else {cin >> x >> y;cout << query(y) - query(x - 1) << "\n";}}}

2.区间修改+单点查询

我们使用差分的思想来建树，我们知道，差分的前缀和是单个点的值。
因此，我们对 $1 - i$ 的差分数组求一次前缀和就能得到 $a [i]$ 的值了，而修改操作就类似于差分的修改，在左右两端修改即可，即在 $i$ 处 $+ x$ 、 $i + 1$ 处 $- x$ 。
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 1e5 + 10;
int c[maxn];//树状数组
int a[maxn]; //原数组
int n,m;
inline int lowbit(int x) {return x & (-x);
}
void add(int i,int x) {while (i <= n) {c[i] += x;i += lowbit(i);}
}
//查找1-i的区间和
int query(int i) {int res = 0;while (i > 0) {res += c[i];i -= lowbit(i);}return res;
}
void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];add(i,a[i]-a[i-1]); //差分建树}while (m--) {int op, l, r,x;cin >> op;if (op == 1) {cin >> l >> r>>x;add(l, x);add(r + 1, -x);}else {cin >>l;cout << query(l)<< '\n';}}
}
signed main() {   ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//FILE* stream;//freopen_s(&stream, "stdcin.txt", "r", stdin);int t = 1;//cin >> t;while (t--) {solve();}//fclose(stdin);}

3.区间修改+区间查询

操作 $(1)$ 是区间修改,操作 $(2)$ 是区间查询。

首先,求区间和 $s u m (L, R) = a [L] + a [L ＋ 1] + \dots + a [R] = s u m (1, R) - s u m (1, L - 1)$ ，问题转换为求 $s u m (1, k)$ 。

定义一个差分数组 $D$ ,它和原数组 $a$ 的关系仍然是
$D [k] = a [k] - a [k - 1]$ ,
$a [k] = D [1] + D [2] ＋ \dots + D [k]$ 。

下面推导区间和,看它与求前缀和有没有关系,如果有关系,就能用树状数组。

$a_1+a_2＋…+a_k$
$D_1+(D_1+D_2)＋(D_1+D_2+D_3)＋…＋(D_1+D_2+…＋D_k)$
$kD_1+(k-1)D_2+(k-2)D_3,+…＋(k-(k-1))D_k,$
$k(D_1+D_2＋…＋D_k)-(D_2+2D_3＋…+(k-1)D_k)$
$=k\sum_{i=1}^{k} D_i-\sum_{i=1}^{k}(i -1)D_i$

公式最后一行求两个前缀和,用两个树状数组分别处理，一个实现 $D_i$ ,另一个实现 $i-1)D_i$ 。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
#define int long long
int n, m;
int tree1[maxn]; //差分树状数组
int tree2[maxn]; //(i-1)*tree1[i]树状数组
int a[maxn]; //原数组
/* 树状数组 */
inline int lowbit(int x) { //神奇的lowbit函数！return x & (-x);
}
/* 维护两个树状数组 */
//区间修改1
void add1(int i, int x) {while (i <= n) {tree1[i] += x;i += lowbit(i);}
}
//区间修改2
void add2(int i, int x) {while (i <= n) {tree2[i] += x;i += lowbit(i);}
}//区间查询1
int query1(int i) {int res = 0;while (i > 0) {res += tree1[i];i -= lowbit(i);}return res;
}
//区间查询2
int query2(int i) {int res = 0;while (i > 0) {res += tree2[i];i -= lowbit(i);}return res;
}
signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];add1(i, a[i] - a[i - 1]); //差分建树add2(i, (i - 1) * (a[i] - a[i - 1]));//(i-1)*tree1[i]建树}while (m--) {int op, x, y, k;cin >> op;if (op == 1) {cin >> x >> y >> k; //修改区间add1(x, k);add1(y + 1, -k);add2(x, (x - 1) * k);add2(y + 1, y * (-k));}else {cin >> x >> y;cout << y * query1(y) - (x - 1) * query1(x - 1) - (query2(y) - query2(x - 1)) << "\n"; //区间查询}}}

三、树状数组的扩展应用

1.树状数组求二维偏序（逆序对）

一种方法是通过归并排序来实现，也可以使用树状数组来实现，下面的代码实现了这两种方法：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
#define pii pair<int,int>
#define int long long
int n;
int tree[maxn];
inline int lowbit(int x) {return x & (-x);
}
void add(int i,int x) {while (i <= n) {tree[i] += x;i += lowbit(i);}
}
int query(int i) { int res = 0;while (i > 0) {res += tree[i];i -= lowbit(i);}return res;
}
void solve1() { //逆序对第一种解法-树状数组cin >> n;vector<pii>a(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i].first;a[i].second = i;}//离散化sort(a.begin() + 1, a.end()); vector<int>b(n + 1);for (int i = 1; i <= n; ++i) {b[a[i].second] = i; }int res = 0;for (int i = 1; i <= n; ++i) {add(b[i], 1);res +=query(n) - query(b[i]);}cout << res << endl;
}
int b[maxn]; //辅助数组
int a[maxn]; //原序列
int res = 0; //逆序对的个数
void merge(int l,int mid,int r) { //排序int i = l, j = mid + 1 ;int k = 0;while (i <= mid && j <= r) {if (a[i] > a[j]) {b[++k] = a[j++];res += mid - i + 1; //记录逆序对个数}else {b[++k] = a[i++];}}while (i <= mid) b[++k] = a[i++];while (j <= r) b[++k] = a[j++];for (int i = 1; i <= k; ++i) { //把辅助数组拷贝到原数组a[l + i - 1] = b[i];}
}
void mergesort(int l,int r) { //划分if (l >= r) return; //边界int mid = l + r >> 1;mergesort(l, mid); mergesort(mid + 1, r);merge(l, mid, r);
}
void solve2() { //第二种解法-归并排序cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}mergesort(1, n);cout << res << endl;
}signed main() {//solve1();solve2();return 0;
}

2.树状数组求区间最值

用暴力法求解,复杂度为 $O (MN)$ 。

下面用树状数组求解。

在标准前缀和树状数组中, $t ree [x]$ 中存储的是 $[x - l o w bi t (x) + 1, x]$ 中每个数的和。

在求最值的树状数组中， $t ree [x]$ 记录 $[x 一 l o w bi t (x) + 1, x]$ 内所有数的最大值。

阅读下面内容时,请对照树状数组原理图,如图 $4.11$ 所示。

(1）单点修改:

$u p d a t e (x, v a l u e)$ 。用 $v a l u e$ 更新 $t ree [z]$ 的最大值,并更新树状数组上被它影响的节点。

例如,修改 $x = 4$ ,步骤如下:

修改 $x$ 子树上直连的 $t ree [2], t ree [3]$ 。

修改 $x$ 的父节点 $t ree [8]$ ,以及 $t ree [8]$ 的直连子节点 $t ree [6]$ , $t ree [7]$ 等。

每步复杂度为 $O(log_2n)$ ,共 $O(log_2n)$ 步,总复杂度为 $O((log_2n)^ 2)$ 。

注意一个特殊情况,初始化时需要修改所有 $n$ 个数,复杂度为 $O(n(log_2n)^2)$ ,符合要求。

$(2)$ 区间最值查询: $q u ery ()$ 。

关于区间 $[L, R]$ 的最值,分两种情况讨论。

$\geq lowbit(R)$

对照图 $4.11$ ,即 $[L, R]$ 区间包含了 $t ree [R]$ 直连子节点的个数,此时直接使用 $t ree [R]$ 值: $q u ery (L, R) = ma x (t ree [R], q u ery (L, R - l o w bi t (R)))$ 。

$2.R-L\leq lowbit(R)$

上述包含关系不成立,先使用 $a [R]$ 的值,然后向前递推: $q u ery (L, R) = ma x (a [R], q u ery (L, R - 1))$ 。

$q u ery ()$ 的复杂度仍然为 $O((log_2n)^2)$ 。

思路

有很多种求区间最值的方法，这里选择使用树状数组来求区间最值，时间复杂度较差，单次修改和查询都为 $O((log_2n)^2)$ ，能通过此题。

代码

const int N = 1e5 + 10;
int a[N];
int tree[N];
int n, m;
void update(int x, int val) {for (int i = x; i <= n; i += lowbit(i)) {tree[i] = val;for (int j = 1; j < lowbit(x); j <<= 1) {tree[i] = std::max(tree[i], tree[i - j]);}}
}int query(int L, int R) {int res = -INF;while (L <= R) {res = std::max(res, a[R]);R--;while (R - L >= lowbit(R)) {res = std::max(res, tree[R]);R -= lowbit(R);}}return res;
}
void solve() {cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];update(i, a[i]);}while (m--) {int l, r;cin >> l >> r;std::cout << query(l, r) << "\n";}}
//main 函数 
signed main() {std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);int t = 1;//cin >> t;while (t--) {solve();}return 0;
}

3.二维区间修改+查询

二维区间修改+查询和一维区间修改+查询类似，都是建立在差分的思想上，二维需要有四个树状数组来维护，具体的推导过程如下：

$(1)$ 二维区间修改

如何实现区间修改?需要结合二维差分数组。定义一个二维差分数组 $D [i] [j]$ ,它与矩阵元素 $a [c] [d]$ 的关系为

$D [i] [j] = a [i] [j] - a [i - 1] [j] - a [i] [j - 1] ＋ a [i - 1] [j - 1]$

对照图 $4.9$ , $D [i] [j]$ 就是阴影面积。

$a[c][d]=\sum_{i=1}^{c} \sum_{j=1}^{d}$ ,可看作对以 $(1, 1)$ 和 $(c, d)$ 为顶点的矩阵内的 $D [i] [j]$ 求和。

它们同样满足“差分是前缀和的逆运算”。

进行区间修改时,在 $u p d a t e ()$ 函数中,每次第 $i$ 行减少 $l o w bi t (i)$ ,第 $j$ 列减少 $l o w bi t (j)$ ,复杂度为 $O(log_2nlog_2m)$ 。

$(2)$ 二维区间查询

查询以 $(a, b)$ 和 $(c, d)$ 为顶点的矩阵区间和,
对照图 $4.10$ 的阴影部分,有
$\sum_{i=a}^{c} \sum_{j=b}^{d} a[i][j]=\sum_{i=1}^{c} \sum_{j=1}^{d} a[i][j]-\sum_{i=1}^{c} \sum_{j=1}^{b-1} a[i][j]-\sum_{i=1}^{a-1} \sum_{j=1}^{d} a[i][j]+\sum_{i=1}^{a-1} \sum_{j=1}^{b-1} a[i][j]$

问题转换为计算 $\sum_{i=1}^{n}\sum_{j=1}^{m}$ ,根据它与差分数组 $D$ 的关系进行变换,有:

$\begin{aligned} & \sum_{i=1}^{n} \sum_{j=1}^{m} a[i][j] \\ = & \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{i} \sum_{l=1}^{j} D[k][l] \\ = & \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times(n-i+1) \times(m-j+1) \\ = & (n+1)(m+1) \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j]-(m+1) \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times i- \\ & (n+1) \sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times j+\sum_{i=1}^{n} \sum_{j=1}^{m} D[i][j] \times i \times j \end{aligned}$

这是 $4$ 个二维树状数组。

代码如下：

思路

使用二维线段树也可以实现，使用二维树状数组比较代码量比较小一点，并且空间复杂度也小一点。

代码

const int N = 2100 + 10;
int tree1[N][N], tree2[N][N], tree3[N][N], tree4[N][N];
char ch;
int n, m;
void update(int x, int y, int val) {for (int i = x; i <= n; i += lowbit(i)) {for (int j = y; j <= m; j += lowbit(j)) {tree1[i][j] += val;tree2[i][j] += x * val;tree3[i][j] += y * val;tree4[i][j] += x * y * val;}}
}int query(int x, int y) {int res = 0;for (int i = x; i > 0; i -= lowbit(i)) {for (int j = y; j > 0; j -= lowbit(j)) {res += (x + 1) * (y + 1) * tree1[i][j] - (y + 1) * tree2[i][j] - (x + 1) * tree3[i][j] + tree4[i][j];}}return res;
}void solve() {cin >> ch >> n >> m;int a, b, c, d;while (cin >> ch >> a >> b >> c >> d) {if (ch == 'L') {int val;cin >> val;update(a, b, val);update(a, d+1, -val);update(c+1, b, -val);update(c+1, d+1, val);}else {std::cout << query(c, d) + query(a - 1, b - 1) - query(a - 1, d) - query(c, b - 1) << "\n";}}}
//main 函数 
signed main() {std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);int t = 1;//cin >> t;while (t--) {solve();}return 0;
}

4.离线算法

这题一种方法是在线通过主席树来做，另一种方法是离线排序后使用树状数组，下面两种方法都实现了：

解法一（主席树）

思路

首先我们需要查询 $[L, R]$ 中不同种类数字的个数。

我们可以在主席树的每个位置存入每个数下一次出现的位置（如果不出现，则存入 $n + 1$ ）。
这样做有什么用呢？

考虑一个区间 $[1, 2, 3, 3, 4, 2, 5]$ ，假设我们要查询区间 $[2, 3, 3]$ ，而我们在主席树中存放的位置为 $[8, 4, 8]$ ，可以发现，我们只需要在主席树上查找区间内大于 $R$ 的数有多少个，而对于这样的查询，主席树显然是很容易做到的。

代码

const int N = 1e6 + 10;
int root[N];
int tot = 0;
struct node {int l, r, cnt;
}tree[N * 40];
#define ls(x) tree[x].l
#define rs(x) tree[x].r
int n;
void build(int l, int r, int& u) {u = ++tot;if (l == r) return;int mid = l + r >> 1;build(l, mid, ls(u));build(mid + 1, r, rs(u));
}
void insert(int u, int& v, int l, int r, int val) {v = ++tot;tree[v] = tree[u];tree[v].cnt++;if (l == r) return;int mid = l + r >> 1;if (val <= mid) {insert(ls(u), ls(v), l, mid, val);}else {insert(rs(u), rs(v), mid + 1, r, val);}
}
int query(int u, int v, int l, int r, int k) {if (l == r) return tree[v].cnt - tree[u].cnt;int res = 0;int s = tree[rs(v)].cnt - tree[rs(u)].cnt;int mid = l + r >> 1;if (k <= mid) {res += s;res += query(ls(u), ls(v), l, mid, k);}else res += query(rs(u), rs(v), mid+1, r, k);return res;
}
int a[N], head[N], nxt[N];
void solve() {cin >> n;build(1, n+1, root[0]);memset(head, -1, sizeof(head));for (int i = 1; i <= n; ++i) {cin >> a[i];if (head[a[i]] == -1) head[a[i]] = i;else {int t = head[a[i]];head[a[i]] = i;nxt[t] = i;}}for (int i = 1; i <= n; ++i) {if (!nxt[i]) nxt[i] = n + 1;insert(root[i - 1], root[i], 1, n + 1, nxt[i]);}int q;cin >> q;while (q--) {int l, r;cin >> l >> r;int res = query(root[l - 1], root[r], 1, n + 1, r + 1);cout << res << "\n";}
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(0);int t = 1;//cin >> t;while (t--) {solve();}
}

解法二（离线+树状数组）

思路

首先我们把序列存起来，按照右端点从小到大排序。
为什么呢？
考虑一段区间 $[1, 2, 3, 3, 4, 2, 5]$ ，我们依次从左到右存入相应位置上（下标 $i$ ）的 $1$ ，在序列 $[1, 2, 3]$ 中，树状数组中的序列为： $[1, 1, 1]$ 。
如果我们发现出现了重复的数字，我们对 $l a s t [a [i]]$ 的位置贡献 $- 1$ ，然后在当前位置加上贡献，此时序列为： $[1, 1, 0, 1]$ 。
可以发现这样的操作类似于差分序列，但是这样的修改会影响到右端点为 $3$ 的查询。
但是我们开头说了：

首先我们把序列存起来，按照右端点从小到大排序

因此我们修改后，就不再存在有右端点小于当前位置 $i$ 的查询了，因此这样的修改是有效的。
所以我们要维护的就是每个数上一次出现的位置了。

代码

const int N = 1e6 + 10;
int n;
int tree[N];
void add(int i, int val) {while (i <= n) {tree[i] += val;i += lowbit(i);}
}
int query(int i) {int res = 0;while (i > 0) {res += tree[i];i -= lowbit(i);}return res;
}
int a[N];
struct node {int l, r, id;bool operator<(node& x) {if (r != x.r) return r < x.r;return l < x.l;}
}q[N];
int res[N], pre[N];
void solve() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}int Q;cin >> Q;for (int i = 1; i <= Q; ++i) {int l, r;cin >> l >> r;q[i] = { l,r,i };}sort(q + 1, q + 1 + Q);int now = 1;for (int i = 1; i <= Q; ++i) {int l = q[i].l, r = q[i].r;for (int j = now; j <= r; ++j) {if (!pre[a[j]]) {pre[a[j]] = j;add(j, 1);}else {add(pre[a[j]], -1), add(j, 1);pre[a[j]] = j;}}now = r + 1;int s = query(r) - query(l - 1);res[q[i].id] = s;}for (int i = 1; i <= Q; ++i) cout << res[i] << "\n";}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(0);int t = 1;//cin >> t;while (t--) {solve();}
}