【算法进阶详解 第一节】树状数组

前言

树状数组在算法竞赛中十分常见，其能解决二维数点，区间数颜色等问题，还具有较小的常数，是一个十分优秀的数据结构。如果文章有问题欢迎在评论区指出。

树状数组基础

树状数组原理

我们用前缀和问题引入树状数组。
给定一个长为 $n$ 数组，之后有 $q$ 次操作，操作分修改和查询两种，修改数组中一个位置，查询前缀和。
如果维护整个数组，每一次修改是 $O(1)$ 的，但是查询要便利整个前缀，复杂度 $O(n)$，$1s$ 难以通过；如果维护前缀和，每一次查询是 $O(1)$ 的，但是修改会影响到包含它的前缀的值，复杂度 $O(n)$，$1s$ 内仍旧难以通过；而树状数组可以在 $O(\log (n))$ 的时间内解决修改和查询两种做法，复杂度十分优秀，相当于平均了修改和查询的复杂度。

	维护数组	维护前缀和	维护树状数组
修改	$O(1)$	$O(n)$	$O(\log (n))$
查询	$O(n)$	$O(1)$	$O(\log (n))$

树状数组中每一个元素 $c_i$ 存储的是 $i-lowbit(i)+1$ ~ $i$ 的权值和，其中 $lowbit(x)$ 表示 $x$ 从低位开始的第一个 $1$ 的权值（即 $2^{最低位算0位时的位数}$），形象表示如下图（来自网上一张图片）：

其中树状数组中每个元素的值就是其所属区间覆盖的原数组的元素和。

对于修改第 $i$ 位操作，修改任意一个位置上的值，变化的是包含其的所有区间，通过找规律可以发现就是 $i$ 从查询位置编号开始，每次加上 $lowbit(i)$。
对于查询前 $i$ 位操作，查询那些区间能覆盖查询操作，通过找规律可以发现就是 $i$ 从查询位置编号开始，每次减去 $lowbit(i)$。

树状数组的核心代码如下：

int lowbit(int x)
{return x & -x;
}void add(int x, int c)
{for (int i = x; i <= n; i += lowbit(i)) tr[i] += c; // n 为数组长度，tr为树状数组。
}int sum(int x)
{int res = 0;for (int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}

树状数组能够解决的问题

树状数组可以解决区间和问题，查询两个前缀和相减即可；树状数组还可以进行单点与原来取 $min$，查询前缀最小值，但是由于两个前缀最小值不能得到区间最小值，所以树状数组这样做不能得到区间最小值。

树状数组提高

树状数组区间加，区间和操作

题目链接

要求实现两种操作：

1. 将一个区间中所有数加上一个数。
2. 查询一个区间中所有数的和。

这个题直接把区间修改暴力拆成单点修改显然会超时。我们可以将原序列 $a$ 变成差分序列 $b$，这样区间 $[l,r]$ 加上 $x$ 就变成了将差分序列的第 $l$ 项加上 $x$，将第 $r+1$ 项减去 $x$，单点查询就变成了前缀查询。若此时把区间查询暴力拆成单点查询，仍旧难以通过。
我们把前缀和式子进行变换：
$$\sum _{i=1}^x{a}_i$$
$$=\sum _{i=1}^x\sum _{j=1}^i{b}_j$$
$$=\sum _{i=1}^x(x-i+1)b_i$$
$$=(x+1)\sum _{i=1}^x{b}_i-\sum _{i=1}^{x}i{b}_i$$
于是我们维护两个树状数组，分别储存 $b_i$ 和 $i{b}_i$ 的前缀和，即可查询原序列的前缀和。两个前缀和相减就是题目中要求查询的区间和了。

二维树状数组

二维树状数组就是把一维树状数组扩展到二维中，能够进行单点修改和二维前缀和查询，具体做法就是把每个一维树状数组的元素再存一个新的一维树状数组。修改时枚举需要修改的树状数组，每个树状数组单独修改；查询时枚举需要查询的树状数组，每个树状数组单独查询即可。设查询和修改的二维平面大小为 $n\times m$，则二维树状数组时间复杂度为 $O(log(n)log(m))$。

二维树状数组的核心代码如下：

int lowbit(int x)
{return x & -x;
}void add(int x, int y, int c)
{for (int i = x; i <= n; i += lowbit(i))for (int j = y; j <= m; j += lowbit(j))tr[i][j] += c;
}int sum(int x, int y)
{int res = 0;for (int i = x; i; i -= lowbit(i))for (int j = y; j; j -= lowbit(j))res += tr[i][j];return res;
}

树状数组应用

树状数组区间数颜色

原题链接

给定一个长度为 $n$ 的数组，每次查询一个区间 $[l,r]$ 中不同值的个数。

直接在线做比较困难，考虑离线，按右端点排序，从前往后按右端点扫描线。在树状数组中，我们在最后一次出现的颜色对应的下标存 $1$，否则存 $0$，扫描线时加入一个颜色时，如果之前没有出现过这个颜色就直接把当前位置加 $1$，否则把前面最后一次出现当前颜色的下标减 $1$，再把当前下标加上 $1$，查询时直接查询区间和即可。

树状数组二维偏序

树状数组可以解决二维偏序问题。

所谓的二维偏序，就是给定两个 $1$ ~ $n$ 的数组 $a$ 和 $b$，对于每个 $1\le i\le n$，计算满足如下条件的 $j(1\le j\le n)$：

1. $a_i\le a_j$
2. $b_i\le b_j$

具体解决方法，可以先把所有下标以 $a_i$ 为第一关建字，$b_i$ 为第二关键字排序，然后从前往后扫描每个下标，当扫描到 $a_i$ 时可能的 $j$ 只能出现在 $i$ 之前（满足第一个限制），且 $i$ 后面不会在有 $j$（后面只有两种情况， $a_i>a_j$ 和 $a_i=a_j$，第一种肯定不满足，第二种因为第二关键字是 $b_i$，所以后面只可能 $b_i\ge b_j$，$b_i>b_j$ 肯定不行，$b_i=b_j$ 特判即可）。

然后由于 $i$ 之前 $a_i$ 的限制一定满足，所以只需处理 $i$ 之前的下标 $b_i$ 的限制即可。我们发现就是求 ${\sum }_{k=1}^{b_i-1}i之前=k的数的个数$。我们把这个式子理解成前缀和，维护一个数组，每扫过一个数就把 $b_i$ 为下标的位置 $+1$，查询前缀和，可以用树状数组处理。时间复杂度 $O(n\log (n)+n\log (\max b_i))$，如果 $\max b_i$ 太大，可以先把 $b_i$ 离散化再求解，复杂度 $O(n\log (n))$。