树状数组
何为树状数组？
首先，树状数组是用来维护序列的前缀和的。
其次，我们要知道树状数组是如何将大区间拆分成一堆小区间的。
比如 \(7 = 111_{(2)}\)，我们可以将其拆分为 \([1,4], [5, 6], [7, 7]\)，再比如 \(12 = 1100_{2}\)，我们可以将其拆分为 \([1, 8],[9, 12]\)。
所以对于一个数 \(x\)，我们每次可以将其拆分为 \([x - lowbit(x) + 1, x]\) 的小区间，然后将 \(x = x - lowbit(x)\)。
那么对于树状数组 \(tr[x]\) 来说，它存的就是 \([x - lowbit(x) + 1, x]\) 的和，比如 \(tr[6]\) 存的是 \([5, 6]\)。
如何查询呢？
假设我们要查询 \([1, x]\) 的前缀和，我们可以从 \(x\) 开始：
- 加上 \(tr[x]\)
- 令 \(x = x - lowbit(x)\)
- 循环以上操作，直到 \(x = 0\)。
一个简单的例子：\([1,15]\) 的前缀和就等于 \(tr[15] + tr[14] + tr[12] + tr[8]\)
如何单点增加呢？
假设我们要在 \(A_x\) 上加 \(y\) 我们只要让所有包含 \(A_x\) 的 \(tr\) 加上 \(y\) 即可。集体操作如下：
- \(tr[x]\) 加上 \(y\)
- 令 \(x = x + lowbit(x)\)
- 循环以上操作，直到 \(x > n\)。
如何建树呢？
假设要对于 \(A_1\sim A_n\) 构造一个树状数组，那么我们只要对于每个 \(i\) 都做一次单点修改，加上 \(A_i\) 即可。
如何区间修改呢？
我们可以使用差分，用树状数组维护差分数组 \(b\)，每次 \(b_l + d, b_{r + 1} - d\)，就相当于 \(add(l, d)\) 和 \(add(r + 1, -d)\)。
如何区间查询呢？
我们观察 y 总画的图，其中 \(b\) 是差分数组。我们发现，蓝色就等于一整个方框减去红色，即：
\((x+1)\sum^{n}_{i = 1}b_i - \sum^{n}_{i = 1}i \times b_i\)
我们可以用两个树状数组分别维护 \(\sum^{n}_{i = 1}b_i\) 和 \(\sum^{n}_{i = 1}i \times b_i\)。
树状数组可以求逆序对
假设有一个序列 \(A\)，我们在 \(A\) 的值域范围上构造树状数组，即对于每个 \(A_i\) 执行一遍 \(add(A_i, 1)\)。
统计逆序对的时候，我们只要返回 \(query(A_i - 1)\) 即可。
这个复杂度是 \(O(N+M)logM\) 的，其中 \(M\) 是值域大小。
来看一些蓝书上的例题。
241. 楼兰图腾 - AcWing题库
我们运用类似于求逆序对的思路，对于 \(A_i\)，求出 \(A_1 \sim A_{i - 1}\) 内小于它的数的数量 \(small1[i]\) 和大于的数量 \(big1[i]\)，再倒着求出 \(A_{i + 1} \sim A_n\) 内的 \(small2[i]\) 和 \(big2[i]\)。
我们以 ^ 为例，它的数量就是 \(\sum^{n}_{i = 1} small1[i] \times small2[i]\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, a[N];
LL tr[N], big[N], small[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
LL query(int x) {
LL res = 0;
for (; x; x -= lowbit(x)) res += tr[x];
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) {
int x = a[i];
big[i] = query(n) - query(x);
small[i] = query(x - 1);
add(x, 1);
}
memset(tr, 0, sizeof tr);
LL res1 = 0, res2 = 0;
for (int i = n; i; i --) {
int x = a[i];
res1 += big[i] * (query(n) - query(x));
res2 += small[i] * query(x - 1);
add(x, 1);
}
printf("%lld %lld\n", res1, res2);
return 0;
}
242. 一个简单的整数问题 - AcWing题库
就是上文中提到的区间修改+单点查询。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += tr[x];
return res;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) {
int b = a[i] - a[i - 1];
add(i, b);
}
while (m --) {
char op[2];
scanf("%s", op);
if (*op == 'C') {
int l, r, d; scanf("%d%d%d", &l, &r, &d);
add(l, d); add(r + 1, -d);
} else {
int x; scanf("%d", &x);
printf("%d\n", query(x));
}
}
return 0;
}
243. 一个简单的整数问题2 - AcWing题库
区间查询+区间修改
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m, a[N];
LL tr1[N], tr2[N];
int lowbit(int x) {
return x & -x;
}
void add(LL tr[], int x, LL c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
LL query(LL tr[], int x) {
LL res = 0;
for (; x; x -= lowbit(x)) res += tr[x];
return res;
}
LL prefix_sum(int x) {
return query(tr1, x) * (x + 1) - query(tr2, x);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) {
int b = a[i] - a[i - 1];
add(tr1, i, b);
add(tr2, i, (LL)i * b);
}
while (m --) {
char op[2]; int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (*op == 'C') {
scanf("%d", &d);
add(tr1, l, d); add(tr2, l, (LL)l * d);
add(tr1, r + 1, -d); add(tr2, r + 1, (LL)(r + 1) * -d);
} else {
printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
}
return 0;
}
244. 谜一样的牛 - AcWing题库
很有意思的一道题。
我们发现对于 \(i\) 来说，它对应的牛就应该是剩下未选择的牛中第 \(A_i + 1\) 大的牛。
什么是未选择的牛？假设当前牛为 \(1 \sim 5\)，且已经选择了 \(2, 4\)，那么 \(1,3,5\) 就是未选择的牛，\(3\) 就是第二大的牛。
想通了之后就很好维护了，我们维护一个树状数组，最开始从 \(1\sim n\) 执行 \(add(i, 1)\)，然后每选择一只牛 \(x\) 就 \(add(x, -1)\)。我们发现 \(query(x)\) 就是当前 \(1\sim x\) 中未选择牛的数量。找第 \(A_i + 1\) 大的牛就显然可以二分。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, a[N];
int tr[N], ans[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += tr[x];
return res;
}
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) add(i, 1);
for (int i = n; i; i --) {
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (query(mid) < a[i] + 1) l = mid + 1;
else r = mid;
}
add(l, -1);
ans[i] = l;
}
for (int i = 1; i <= n; i ++) printf("%d\n", ans[i]);
return 0;
}
浙公网安备 33010602011771号