0%

树状数组学习笔记(二)

树状数组一些不那么裸的操作。

区间修改

我们已经知道了单点修改怎么做,但是怎么区间修改呢?

考虑差分。

现在已知差分数组 diff[i] = a[i] - a[i - 1],求每个点的值其实就是求这个点在差分数组中的前缀和。

所以此时每个结点存的不是原数组,而是差分数组,更新的时候按照差分的思路更新即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

int t[500010];
int n, m, diff, x, opt, y, k;

int lowbit(int x) { return x & -x; }

void update(int pos, int d) {
while (pos <= n) {
t[pos] += d;
pos += lowbit(pos);
}
return ;
}

int query(int pos) {
int s = 0;
while (pos) {
s += t[pos];
pos -= lowbit(pos);
}
return s;
}

int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
read(x);
update(i, x - diff);
diff = x;
}
while (m--) {
read(opt);
if (opt == 1) {
read(x), read(y), read(k);
update(x, k), update(y + 1, -k);
} else {
read(x);
printf("%d\n", query(x));
}
}
return 0;
}

上面的代码只能单点查询,接下来讨论区间查询的情况:

已知原数组 $a$,差分数组 $b$,且 $a_i = \sum_{j=1}^{i}b_j$。

区间查询就意味着用到 $a$ 的前缀和相减,所以还要对 $a$ 建树。假设现在求 $p$ 的前缀和。

即我们只需要维护 $\sum b_i$ 和 $\sum ib_i$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

typedef long long LL;

LL t[1000010], g[1000010];
LL n, q, x, l, r, opt, last;

inline LL lowbit(LL x) { return x & -x; }

void update(LL pos, LL d) {
int tmp = pos;
while (pos <= n) {
t[pos] += d, g[pos] += d * tmp;
pos += lowbit(pos);
}
return ;
}

LL query(LL pos) {
LL s = 0, tmp = pos;
while (pos) {
s += (tmp + 1) * t[pos] - g[pos];
pos -= lowbit(pos);
}
return s;
}

int main() {
read(n), read(q);
for (int i = 1; i <= n; ++i) {
read(x);
update(i, x - last);
last = x;
}
while (q--) {
read(opt);
if (opt == 1) {
read(l), read(r), read(x);
update(l, x), update(r + 1, -x);
} else {
read(l), read(r);
printf("%lld\n", query(r) - query(l - 1));
}
}
return 0;
}

求逆序对

逆序对也是树状数组的一个应用。

考虑逆序对的定义:对于两个数 $i, r$,如果 $a_i > a_r$ 且 $i < r$ 则称这个东西为逆序对。

可以用总数减去非严格顺序对的个数得到这个答案。

现在结点表示的不是 $a_i$,而是 $i$ 出现过几次。

举个例子,第 $i$ 个数为 $a_i$,修改并不是 update(i, a[i]),而是 update(a[i], 1)

每次求 $a_i$ 的前缀和,就得到了当前非严格顺序对的个数。

一般还需要离散化。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

typedef long long LL;

struct Node {
int val, id;
friend bool operator < (const Node &a, const Node &b) {
if (a.val == b.val) return a.id < b.id;
return a.val < b.val;
}
} b[500010];

LL a[500010], t[500010];
LL ans;
int n;

inline int lowbit(int x) { return x & -x; }

void update(int pos, int d) {
while (pos <= n) {
t[pos] += d;
pos += lowbit(pos);
}
}

LL query(int pos) {
LL s = 0;
while (pos) {
s += t[pos];
pos -= lowbit(pos);
}
return s;
}

int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(b[i].val);
b[i].id = i;
}
std::sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i) a[b[i].id] = i;
for (int i = 1; i <= n; ++i) {
update(a[i], 1);
ans += i - query(a[i]);
}
printf("%lld\n", ans);
return 0;
}

建树优化

设当前结点为 $x$,子结点为 $s$,不难发现 $x = \sum t_s$。

所以在建树时直接对自己和自己的父亲进行操作即可。

能将建树的时间复杂度优化到 $O(n)$。

代码:

1
2
3
4
5
6
7
inline int lowbit(int x) { return x & -x; }

for (int i = 1; i <= n; ++i) {
read(x);
t[i] += x;
if (i + lowbit(i) <= n) t[i + lowbit(i)] += x;
}

例题

LOJ #130. 树状数组 1 :单点修改,区间查询

LOJ #131. 树状数组 2 :区间修改,单点查询

LOJ #132. 树状数组 3 :区间修改,区间查询

洛谷 P3374 【模板】树状数组 1

洛谷 P3368 【模板】树状数组 2

一维树状数组的几道模板题。

洛谷 P1908 逆序对

可以用来写逆序对的题。