树状数组
其实假如你会线段树,并且比较熟练,你可以直接离开。
为什么呢?
虽然线段树和树状数组的基础功能是差不多的,但是 — 树状数组能做到的操作线段树一定能做到,但是线段树能做的事情树状数组不一定能做到。
虽然话是这么说,但是在实际赛场上,树状数组性价比是很高的。尽管树状数组功能没有线段树那么多,但是树状数组的代码长度以及思维难度都是比线段树低的。
假如题目只需要单点修改的话,树状数组绝对是我十分推荐的选择。
概念
上图为树状数组原理示意图。
设用 \(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
- 《算法竞赛(罗勇军、郭卫斌)》