树状数组
其实假如你会线段树，并且比较熟练，你可以直接离开。
为什么呢？
虽然线段树和树状数组的基础功能是差不多的，但是 — 树状数组能做到的操作线段树一定能做到，但是线段树能做的事情树状数组不一定能做到。
虽然话是这么说，但是在实际赛场上，树状数组性价比是很高的。尽管树状数组功能没有线段树那么多，但是树状数组的代码长度以及思维难度都是比线段树低的。
假如题目只需要单点修改的话，树状数组绝对是我十分推荐的选择。
概念
上图为树状数组原理示意图。
设用 \(a\) 表示原序列，\(c\) 如图所示。
则我们可以得出：
\(c_1 = a_1\)；
\(c_2 = c_1 +a_2\)；
\(c_3 = a_3\)；
\(c_4 = c_2 + c_3 + a_4\)；
\(c_5 = a_5\)；
\(c_6 = c_5 + a_6\)；
\(c_7 = a_7\)；
\(c_8 = c_4 + c_6 + c_7 + a_8\)。
再设 \(k\) 表示 \(i\) 的二进制中从最低位往高位连续零的长度。
便可以得到 \(c_i = a_{i - 2^k + 1} + a_{i - 2^k + 2} + \cdots + a_i\)。
现在问题来了，如何求出 \(k\) 呢？最低位往高位连续零的长度其实也相当于求 1 的最低位。所以便有神仙想出了 lowbit(x) = x & (-x)。
为什么可以这样写呢？
分析 x & (-x) 这个式子。
根据计算机补码的性质（补码就是原码的反码加一）：
例如 \(10\)，
原码：\((10)_{10} = (1010)_2\)；
反码：\((0101)_2\)；
补码：\((0110)_2\)。
不难发现，反码与原码的每一位都不相同。但是当反码加上一之后，会一直进位直到遇到 \(0\)，这个 \(0\) 就变成了 \(1\)（下文称该 \(1\) 为特殊数），这时这个数末尾就构造了一个 10000... 串。由于补码是由反码加一的来的，所以除了变成 \(1\) 的 \(0\) 以外，其他的数位都是不相等的。所以可以发现特殊数以前的部分补码与原码相反；特殊数的位置补码与原码都是 \(1\)；特殊数以后的部分补码与原码都是 \(0\)。所以 \(\texttt{lowbit}(x)\) 就等于 \(k\)。
这样 \(k\) 就轻松地求出来了。
基本操作
单点修改，区间查询。
修改
设想一下，要更改 \(a_x\) 的值，就必须要把所有包含了 \(a_x\) 的 \(c\) 修改。
那我们如何来找到所有包含了 \(a_x\) 的 \(c\) 呢？我们可以发现一个规律：就是 包含 \(a_x\) 的唯一元素的下标 \(= a_x + \texttt{lowbit}(x)\)。
void modify(int i, int v)
{
while (i <= n)
{
c[i] += v;
i += lowbit(i);
}
}
查询
利用前缀和的思想，想查询 \([l, r]\) 的和，只需要用 \(sum_r - sum_{l-1}\) 就可以了。
所以树状数组的查询实际上就利用了前缀和的思想。与修改相反，查询要从顶端向低端跳，所以相对应的求 \([1, x]\) 的区间只要让 \(x\) 每次都减去 \(\texttt{lowbit}(x)\) 就行了。
int query(int x)
{
int ans = 0;
while (x >= 1)
{
ans += c[x];
x -= lowbit(x);
}
return ans;
}
【模板】树状数组 1
这道题就是树状数组的模板，把上述操作代码复制即可。
如何建树状数组呢？刚开始时树状数组初始为 \(0\)，只需要将每个节点加上题目给定的初始值就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
long long c[maxn];
int n, m;
int lowbit(int x)
{
return x & (-x);
}
void modify(int x, int k)
{
while (x <= n)
{
c[x] += k;
x += lowbit(x);
}
}
long long query(int x)
{
long long res = 0;
while (x > 0)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int x;
cin >> x;
modify(i, x);
}
for (int i = 1; i <= m; i ++)
{
int opt, x, y;
cin >> opt >> l >> r;
if (opt == 1)
modify(l, r);
if (opt == 2)
cout << query(r) - query(l - 1) << endl;
}
return 0;
}
时间复杂度：
- 构造数组：
- 暴力：从 \(1\) 到 \(n\) 循环，时间复杂度 \(O(n)\)。
- 树状数组：\(n\) 次修改，时间复杂度 \(O(n \log n)\)。
- 修改：
- 暴力：直接修改，时间复杂度 \(O(1)\)。
- 树状数组：从下往上跳，时间复杂度 \(O(\log n)\)。
- 查询：
- 暴力：从 \(l\) 到 \(r\)，时间复杂度 \(O(n)\)。
- 树状数组：从上往下跳，时间复杂度 \(O(\log n)\)。
- 总复杂度：
- 暴力：\(O(nm)\)。
- 树状数组：\(O((n+m)\log n)\)。
差分树状数组
差分树状数组可以实现区间修改，单点查询。
具体怎么实现呢？其实树状数组的基本操作是不用改的，只是在做操作时调用函数的方式有所不同。并且这些操作用线段树代码非常冗长，但是树状数组却简洁明了。
考虑使用差分数组，维护树状数组序列。
假设直接用差分数组维护序列。
for (int i = 1; i <= n; i ++)
{
scanf("%d", &q[i]);
d[i] = q[i] - q[i - 1];
}
while (q --)
{
int opt;
scanf("%d", &opt);
if (opt == 1)
{
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
d[x] += k;
d[y + 1] -= k;
}
else
{
int x;
scanf("%d", &x);
for (int i = 1; i <= n; i ++)
q[i] = q[i - 1] + d[i];
printf("%d", q[x]);
}
}
那差分树状数组怎么实现呢？只需要用树状数组代替 \(d\) 序列就行了。并且用树状数组不仅能够很好地支持 \(d\) 序列的操作，并且比 \(d\) 序列快。
构造
和单点修改，区间查询的操作一样，只不过是要赋 \(q_i - q_{i - 1}\) 的值。并且后文并不需要用到数组 \(q\)，所以我们考虑滚动数组实现。
int u, v = 0;
for (int i = 1; i <= n; i ++)
{
scanf("%d", &u);
modify(u - v);
v = u;
}
修改
通过差分的思想，将第 \(l\) 个数加上 \(k\)，将第 \(r + 1\) 个数减去 \(k\)。
modify(l, k);
modify(r + 1, -k);
查询
要查询第 \(x\) 个数，直接对树状数组进行一次前缀和操作即可，并且操作到第 \(x\) 个数就可以了。
printf("%d", query(x));
没错，就是这么简单。
【模板】树状数组 2
这也是差分树状数组的模板，直接将上述操作代码复制即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
long long c[maxn];
int n, m;
int lowbit(int x)
{
return x & (-x);
}
void modify(int x, int k)
{
while (x <= n)
{
c[x] += k;
x += lowbit(x);
}
}
long long query(int x)
{
long long res = 0;
while (x > 0)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
int main()
{
cin >> n >> m;
int u, v = 0;
for (int i = 1; i <= n; i ++)
{
scanf("%d", &u);
modify(i, u - v);
v = u;
}
int opt;
while (m --)
{
cin >> opt;
if (opt == 1)
{
int x, y;
long long k;
cin >> x >> y >> k;
modify(x, k);
modify(y + 1, -k);
}
else if (opt == 2)
{
int x;
cin >> x;
cout << query(x) << endl;
}
}
return 0;
}
时间复杂度：
- 构造数组：
- 普通差分：从 \(1\) 到 \(n\) 循环，时间复杂度 \(O(n)\)。
- 差分树状数组：\(n\) 次修改，时间复杂度 \(O(n \log n)\)。
- 修改：
- 普通差分：直接修改，时间复杂度 \(O(\log n)\)。
- 差分树状数组：执行两次
add操作，时间复杂度 \(O(\log n)\)。
- 查询：
- 普通差分：执行前缀和操作，时间复杂度 \(O(n)\)。
- 差分树状数组：执行一次
sum操作，时间复杂度 \(O(\log n)\)。
- 总复杂度：
- 普通差分：\(O(nm)\)。
- 差分树状数组：\(O(m \log n)\)。
参考文献
- OI Wiki
- Luogu Blog 1
- Luogu Blog 2
- Luogu Blog 3
- Luogu Blog 4
- Luogu Blog 5
- 《算法竞赛（罗勇军、郭卫斌）》