几道 线段树&树状数组 的题

发现以前会的好多算法现在都忘得差不多了。。。翻了翻以前写过的一些比较复杂的题目,发现现在真是两眼一抹黑。

准备有空重新开始刷一波题。

先开个线段树的专题吧。


整理了一下模版,快速过了 4 个典型例题。

经典例题

HDU1166

【线段树/树状数组】

单点更新,区间求和。

嗯,树状数组天生就是做这个的,没啥说的。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 1166
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c[50000];
int n;
int lowbit(int s)
{
return s&-s;
}
void update(int s,int x)
{
while (x<=n)
{
c[x]+=s;
x+=lowbit(x);
}
}
int sum(int x)
{
int t=0;
while (x>0)
{
t+=c[x];
x-=lowbit(x);
}
return t;
}
int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
for (int tt=1;tt<=T;tt++)
{
printf("Case %d:\n", tt);
memset(c, 0, sizeof(c));
scanf("%d", &n);
for (int i=1;i<=n;i++)
{
int s;
scanf("%d", &s);
update(s, i);
}
char ss[10];
while(scanf("%s", ss))
{
int i, j;
if (ss[0]!='E')
{
scanf("%d %d", &i, &j);
switch(ss[0])
{
case 'Q':
printf("%d\n", sum(j) - sum(i-1));
break;
case 'A':
update(j, i);
break;
case 'S':
update(-j, i);
break;
}
}
else break;
}
}
return 0;
}

线段树也是基础用法,不过说起来以前我写的线段树基本上都是用的结构体数组,压缩一下子节点的标记号增长方式可以把空间限制在 2N~3N 左右。

这次换了个模版,标号增长直接用的是二叉树倍增的方式,空间要浪费一点,需要开到 4N,不过拿掉了其他多余的东西(结构体等等),好像效果也还好。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 1166
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[50000],ans[4*50000];
void pushup(int rt)
{
ans[rt]=ans[rt<<1]+ans[rt<<1|1];
}
void build(int l,int r,int rt)
{
if (l==r)
{
ans[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void add(int L,int C,int l,int r,int rt)
{
if (l==r)
{
ans[rt]+=C;
return;
}
int mid=(l+r)>>1;
if (L<=mid)
add(L,C,l,mid,rt<<1);
else
add(L,C,mid+1,r,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
return ans[rt];
int mid=(l+r)>>1;
int ANS=0;
if (L<=mid)
ANS+=query(L,R,l,mid,rt<<1);
if (R>mid)
ANS+=query(L,R,mid+1,r,rt<<1|1);
return ANS;
}
int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
for (int tt=1;tt<=T;tt++)
{
printf("Case %d:\n", tt);
int n;
scanf("%d", &n);
for (int i=1;i<=n;i++)
scanf("%d", &a[i]);
memset(ans, 0, sizeof(ans));
build(1, n, 1);
char ss[10];
while(scanf("%s", ss))
{
int i, j;
if (ss[0]!='E')
{
scanf("%d %d", &i, &j);
switch(ss[0])
{
case 'Q':
printf("%d\n", query(i, j, 1, n, 1));
break;
case 'A':
add(i, j, 1, n, 1);
break;
case 'S':
add(i, -j, 1, n, 1);
break;
}
}
else break;
}
}
return 0;
}

HDU1754

【线段树】

单点更新,区间求最值。

线段树基础用法。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 1754
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[200010], amax[4*200010];
int max(int x, int y)
{
return x>y ? x:y;
}
void build(int l, int r, int rt)
{
if (l == r)
{
amax[rt] = a[l];
return;
}
int mid = (l+r)>>1;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
amax[rt] = max(amax[rt<<1], amax[rt<<1|1]);
}
void update(int L, int C, int l, int r, int rt)
{
if (l == r)
{
amax[rt] = C;
return;
}
int mid = (l+r)>>1;
if (L <= mid)
update(L, C, l, mid, rt<<1);
else
update(L, C, mid+1, r, rt<<1|1);
amax[rt] = max(amax[rt<<1], amax[rt<<1|1]);
}
int query(int L, int R, int l, int r, int rt)
{
if (L<=l && r<=R)
return amax[rt];
int mid = (l+r)>>1;
int temp = 0;
if (L <= mid)
temp = max(temp, query(L, R, l, mid, rt<<1));
if (R > mid)
temp = max(temp, query(L, R, mid+1, r, rt<<1|1));
return temp;
}
int main()
{
freopen("in.txt", "r", stdin);
int n, m;
while(scanf("%d %d", &n, &m)!=EOF)
{
for (int i=1;i<=n;i++)
scanf("%d", &a[i]);
memset(amax, 0, sizeof(amax));
build(1, n, 1);
for (int i=0;i<m;i++)
{
char c;
int x, y;
scanf("\n%c %d %d", &c, &x, &y);
if (c=='Q')
printf("%d\n", query(x, y, 1, n, 1));
else update(x, y, 1, n, 1);
}
}
return 0;
}

HDU1698

【线段树】

区间更新,区间求和。

修改区间的时候就要多加一个 lazy 标记,基础用法。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 1698
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int res[4*100010], lazy[4*100010];
void build(int l, int r, int rt)
{
if (l == r)
{
res[rt] = 1;
return;
}
int mid = (l+r)>>1;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
res[rt] = res[rt<<1] + res[rt<<1|1];
}
void pushdown(int rt, int ln, int rn)
{
if (lazy[rt])
{
lazy[rt<<1] = lazy[rt];
lazy[rt<<1|1] = lazy[rt];
res[rt<<1] = lazy[rt]*ln;
res[rt<<1|1] = lazy[rt]*rn;
lazy[rt] = 0;
}
}
void update(int L, int R, int C, int l, int r, int rt)
{
if (L<=l && r<=R)
{
res[rt] = C*(r-l+1);
lazy[rt] = C;
return;
}
int mid = (l+r)>>1;
pushdown(rt, mid-l+1, r-mid);
if (L <= mid) update(L, R, C, l, mid, rt<<1);
if (R > mid) update(L, R, C, mid+1, r, rt<<1|1);
res[rt] = res[rt<<1] + res[rt<<1|1];
}
int query(int L, int R, int l, int r, int rt)
{
if (L<=l && r<=R)
return res[rt];
int mid = (l+r)>>1;
pushdown(rt, mid-l+1, r-mid);
int temp = 0;
if (L <= mid) temp += query(L, R, l, mid, rt<<1);
if (R > mid) temp += query(L, R, mid+1, r, rt<<1|1);
return temp;
}
int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
for (int tt=1;tt<=T;tt++)
{
int n;
scanf("%d", &n);
memset(res, 0, sizeof(res));
memset(lazy, 0, sizeof(lazy));
build(1, n, 1);
int m;
scanf("%d", &m);
for (int i=0;i<m;i++)
{
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
update(x, y, z, 1, n, 1);
}
printf("Case %d: The total value of the hook is %d.\n", tt, query(1, n, 1, n, 1));
}
return 0;
}

HDU1556

【线段树/树状数组】

区间更新,单点求值。

这是最经典的线段覆盖问题。

单点求值的时候有点不同的是只要用到 lazy 标记就够了,沿着路径一路走到叶子结点,把一路上的 lazy 标记全部加起来就好。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 1556
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int lazy[4*100010];
void pushdown(int rt, int ln, int rn)
{
if (lazy[rt])
{
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
lazy[rt] = 0;
}
}
void update(int L, int R, int l, int r, int rt)
{
if (L<=l && r<=R)
{
lazy[rt] += 1;
return;
}
int mid = (l+r)>>1;
pushdown(rt, mid-l+1, r-mid);
if (L <= mid) update(L, R, l, mid, rt<<1);
if (R > mid) update(L, R, mid+1, r, rt<<1|1);
}
int query(int X, int l, int r, int rt)
{
if (X<=l && r<=X)
return lazy[rt];
int mid = (l+r)>>1;
int temp = lazy[rt];
if (X <= mid) temp += query(X, l, mid, rt<<1);
else temp += query(X, mid+1, r, rt<<1|1);
return temp;
}
int main()
{
freopen("in.txt", "r", stdin);
int n;
scanf("%d", &n);
while (n)
{
memset(lazy, 0, sizeof(lazy));
for (int i=0;i<n;i++)
{
int a, b;
scanf("%d %d", &a, &b);
update(a, b, 1, n, 1);
}
printf("%d", query(1, 1, n, 1));
for (int i=2;i<=n;i++)
printf(" %d", query(i, 1, n, 1));
printf("\n");
scanf("%d", &n);
}
return 0;
}

树状数组解法是把单点求值转化为求前缀和,把区间更新转化为两次单点更新即可。

每次要插一条区间的时候,在区间开头加一,区间结尾减一,这样下次求前缀和的时候就相当于原本的单点求值了。

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
64
65
66
67
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 1556
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c[100010];
int n;
int lowbit(int s)
{
return s&-s;
}
void update(int s,int x)
{
while (x<=n)
{
c[x]+=s;
x+=lowbit(x);
}
}
int sum(int x)
{
int t=0;
while (x>0)
{
t+=c[x];
x-=lowbit(x);
}
return t;
}
int main()
{
freopen("in.txt", "r", stdin);
scanf("%d", &n);
while (n)
{
memset(c, 0, sizeof(c));
for (int i=0;i<n;i++)
{
int a, b;
scanf("%d %d", &a, &b);
update(1, a);
update(-1, b+1);
}
printf("%d", sum(1));
for (int i=2;i<=n;i++)
printf(" %d", sum(i));
printf("\n");
scanf("%d", &n);
}
return 0;
}

再深入一点

翻了下,博客里面以前记过一题,顺便也整理到这里来。然后还有几次以前比赛里面没补的题,看看能不能补一波。

HDU5172

不更新,但是区间判断的东西比较有意思。每次询问的是给个区间,假设区间长度是 n,问这个区间中的数字是不是刚好能从 1 排到 n。

HDU5023

14 年广州网赛的 B 题,当时没怎么写。

30 种颜色,每次用一种颜色涂一些线段,询问一段区间内有什么颜色,把颜色全部列出来。

内心OS:哇。。。这么基础的线段树染色题我当年在干什么。。。捂脸

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : hdu 5023
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int res[4*1000010], lazy[4*1000010];
void build(int l, int r, int rt)
{
if (l == r)
{
res[rt] = 2;
return;
}
int mid = (l+r)>>1;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
res[rt] = res[rt<<1] | res[rt<<1|1];
}
void pushdown(int rt)
{
if (lazy[rt])
{
lazy[rt<<1] = lazy[rt];
lazy[rt<<1|1] = lazy[rt];
res[rt<<1] = lazy[rt];
res[rt<<1|1] = lazy[rt];
lazy[rt] = 0;
}
}
void update(int L, int R, int C, int l, int r, int rt)
{
if (L<=l && r<=R)
{
lazy[rt] = 1 << (C-1);
res[rt] = 1 << (C-1);
return;
}
int mid = (l+r)>>1;
pushdown(rt);
if (L <= mid) update(L, R, C, l, mid, rt<<1);
if (R > mid) update(L, R, C, mid+1, r, rt<<1|1);
res[rt] = res[rt<<1] | res[rt<<1|1];
}
int query(int L, int R, int l, int r, int rt)
{
if (L<=l && r<=R)
return res[rt];
int mid = (l+r)>>1;
pushdown(rt);
int temp = 0;
if (L <= mid) temp |= query(L, R, l, mid, rt<<1);
if (R > mid) temp |= query(L, R, mid+1, r, rt<<1|1);
return temp;
}
int main()
{
freopen("in.txt", "r", stdin);
int n, m;
scanf("%d %d", &n, &m);
while(!(n==0 && m==0))
{
memset(res, 0, sizeof(res));
memset(lazy, 0, sizeof(lazy));
build(1, n, 1);
for (int i=0;i<m;i++)
{
char com;
int a,b;
scanf("\n%c %d %d", &com, &a, &b);
if (com == 'P')
{
int c;
scanf("%d", &c);
update(a, b, c, 1, n, 1);
} else
{
int ans = query(a, b, 1, n, 1);
int count = 1;
bool blank = false;
while (ans)
{
if (ans&1)
{
if (blank) printf(" ");
printf("%d", count);
blank = true;
}
ans = ans >> 1;
count ++;
}
printf("\n");
}
}
scanf("%d %d", &n, &m);
}
return 0;
}

30 种颜色,用位运算可以很方便地表示出来。

嗯。。。下面的 H 题等下次什么时候想把树链剖分翻出来的时候再研究吧。

Show comments from Gitment
0%