树状数组

引入

对于一般的前缀和,我们在对一个值$x$进行修改的时候需要将$x$及$x$之后的前缀和值都进行修改。而最坏情况的时间复杂度达到了$O(n)$.

1
2
3
void add(int x, int y) { //假设在第x个位置的值加y
for (int i = x; i <= n; ++ i) sum[i] += y;
}

但是查询操作就直接返回当前的前缀和值即可。时间复杂度为$O(1)$.

1
2
3
int ask(int x) {
return sum[x];
}

两者平均,均摊复杂度为$O(n)$.
而树状数组就是将修改操作和查询操作的复杂度都平均成了$O(logn)$.
修改操作中我们只需要将当前数x加上$lowbit(x)$,设一个数组c,将$c[x]+=y$即可

1
2
3
void add(int x, int y) {
for (; x <= n; x += x & -x) c[x] += y;
}

查询操作也差不多,但是x要倒叙加$lowbit(x)$.

1
2
3
4
5
int ask(int x) {
int res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}

因为lowbit运算是log级别的,所以两者的时间复杂度均为$O(logn)$.
图片源于网络

例题

模板题

我觉得这题把上面两个代码一抄应该就没什么问题了。

小乔(前几天模拟赛的题)

题目大意:给出三个$n$,$m$,$k$.表示有$n$个扇形(原点相同),将$360°$平均分成$m$份,其中被$k$个扇形以上覆盖的面积*$\frac{2m}{π}$是多少。接下来给出n个扇形的起始位置,结束位置,以及半径。
for example:

样例附图
这组数据就是:

1
2
3
4
5
6
7
Input:
3 8 2
1 -8 8
3 -7 3
5 -5 5
Output:
76

那我们只需把圆剖成一个$max${$ri$}行$2m$列的矩形,枚举起始位置$j=si到终止位置ti$和$k=1到ri$,设一个数组cnt,将$cnt[j,k]++$即可,而对于答案就是枚举矩形的每一列,找到一行使得$cnt[j,k]\geq k$,那么就将 $ans+=k$2即可.
但是这样它的时间复杂度为$O(nmri)$,我们考虑用树状数组优化。我们将每个扇形的起始位置$si$和终止位置$ti$记录下来,用一个类似差分的算法,将$c[s[i]]+=1$,$c[t[i]+1]-=1$.然后对m进行枚举,再二分$k$,用后缀树状数组加上就完了。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100010, M = 200010;
int n, m, k, r[N], s[N], t[N];
ll ans = 0, c[N];
vector<int> v[N << 1][2];

void add(int x, int y) {
for (; x; x -= x & -x) c[x] += y;
}

ll ask(int x) {
ll res = 0;
for (; x <= N - 10; x += x & -x) res += c[x];
return res;
}

int main() {
freopen("xiaoqiao.in", "r", stdin);
freopen("xiaoqiao.out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++ i) {
scanf("%d%d%d", &r[i], &s[i], &t[i]);
s[i] += m, t[i] += m;
if (s[i] < t[i]) {
v[s[i]][0].push_back(r[i]);
v[t[i]][1].push_back(r[i]);
}
else {
v[0][0].push_back(r[i]);
v[m << 1][1].push_back(r[i]);
v[s[i]][0].push_back(r[i]);
v[t[i]][1].push_back(r[i]);
}
}
for (int i = 0; i <= m << 1; ++ i) {
for (int j = 0; j < v[i][0].size(); ++ j) add(v[i][0][j], 1);
for (int j = 0; j < v[i][1].size(); ++ j) add(v[i][1][j], -1);
int l = 1, r = N - 10;
while(l + 1 < r) {
int mid = l + r >> 1;
if (ask(mid) >= k) l = mid;
else r = mid;
}
if (ask(r) >= k) ans += 1LL * r * r;
else if (ask(l) >= k) ans += 1LL * l * l;
}
printf("%lld\n", ans);
return 0;
}

拓展1——二维树状数组

类似于二维前缀和,只要修改和查询操作中的数组各加一维就没了。
修改操作:

1
2
3
4
5
void add(int x, int y, int k) {
for (; x <= n; x += x & -x)
for (int yy = y; yy <= m; yy += yy & -yy) // 保留初始y值
c[x][yy] += k;
}

查询操作:

1
2
3
4
5
6
7
int ask(int x, int y) {
int res = 0;
for (x; x; x -= x & -x)
for (int yy = y; yy; yy -= yy & yy)
res += c[x][yy];
return res;
}

例题

SuperBrother打鼹鼠(vijos1512)

题目就是说有一个$n*n$的矩形,有$m$种操作,$m$种操作有2中类型:
1.将$c[x,y]+=k$;
2.求c数组$(x1,y1)-(x2,y2)$的值。

对第一种操作只需要$add(x+1,y+1,k)$就行了,那么对于第二种操作,类似于前缀和,答案就是$ask(x2+1,y2+1)-ask(x1,y2+1)-ask(x2,y1+1)+ask(x1,y1)$.

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1050;
int n, c[N][N];

ll ask(int x, int y) {
ll sum = 0;
for (; x; x -= x & -x)
for (int yy = y; yy; yy -= yy & -yy)
sum += c[x][yy];
return sum;
}

void add(int x, int y, int z) {
for (; x <= n + 1; x += x & -x)
for (int yy = y; yy <= n + 1; yy += yy & -yy)
c[x][yy] += z;
}

int main() {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
scanf("%d", &n);
int num, x, y, z, x1, y1, x2, y2;
for (; ; ) {
scanf("%d", &num);
if (num == 1) {
scanf("%d%d%d", &x, &y, &z);
add(x + 1, y + 1, z);
}
if (num == 2) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%lld\n", ask(x2 + 1, y2 + 1) + ask(x1, y1) - ask(x1, y2 + 1) - ask(x2 + 1, y1));
}
if (num == 3) return 0;
}
}

拓展2——区间修改,区间查询

普通的树状数组只能用来处理单点修改的操作,那么我们现在需要将树状数组加上一种算法,并且这种算法得是$O(1)$操作的,来进行维护区间操作,很容易想到差分。
如果不要求区间查询操作,我们对于每个修改操作$l,r,k$,只需要让$add(l, k)$和$add(r+1,-k)$,查询时$ask(pos)$即可。
区间修改,单点查询模板题

但是如果这样做的话在区间查询$l,r$时,我们就需要计算 $\sum_{i=l}^{r} ask(i)$,那么这种算法最坏情况下时间复杂度会达到$O(nlogn)$,但是它要求的是一段连续的值,我们可以再用一个树状数组来存储答案。

具体做法如下:
我们在每次进行区间修改$l,r,d$时,用树状数组维护一个差分数组b,使$add(l,d)$,$add(r+1,-d)$.
假设我们要求$\sum_{i=1}^{x}ask(i)$,那么我们将式子进行推导:
$\sum_{i=1}^{x}ask(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} ib[i]$.
所以在修改操作时,对第一个树状数组需要$add(l,d,0)$,$add(r+1,-d,0)$;第二个树状数组需要$add(l,ld,1)$,$add(r+1,(r+1)d,1)$. (第三个参数表示第几个树状数组)
在查询$(l,r)$这个区间时只要返回$((r+1)ask(r,0)-ask(r,1))-(lask(l-1,0)-ask(l-1,1))$即可。

代码实现:

1
2
3
4
5
6
7
8
int ask(int x, int k) {
int res = 0;
for (; x; x -= x & -x) res += c[x][k];
return res;
}
vodi add(int x, int y, int k) {
for (; x <= n; x += x & -x) c[x][k] += y;
}
(A Simple Problem with Integers)模板

完整代码

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 500010;
int n, m;
ll a[N], c[N][2];

ll ask(int x, int k) {
ll sum = 0;
for (; x; x -= x & -x) sum += c[x][k];
return sum;
}

void add(int x, int y, int k) {
for (; x <= n; x += x & -x) c[x][k] += y;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]), a[i] += a[i - 1];
char c[1];
int x, y, z;
for (int i = 1; i <= m; ++ i) {
scanf("%s", c);
if (c[0] == 'C') {
scanf("%d%d%d", &x, &y, &z);
add(x, z, 0);
add(y + 1, -z, 0);
add2(x, x * z, 1);
add2(y + 1, -(y + 1) * z, 1);
}
else {
scanf("%d%d", &x, &y);
printf("%lld\n", (ll)(a[y] - a[x - 1] + ask(y, 0) * (y + 1) - ask(x - 1, 0) * x - ask(y, 1) + ask(x - 1, 1)));
}
}
return 0;
}

拓展3——二维区间修改,区间查询

直接上题吧

A+B Problem

给你一个$n*n$的矩形方格(横纵坐标都为$0-(n-1)$),一开始每个方格中的数都为$0$。你需要支持以下$q$两个操作:
1.将给定的一个矩形中所有数$+1$。
2.询问给定一个矩形内所有数之和对$p$取模。
并强制在线。