Chenfan Blog

Do cool things that matter.

0%

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

Posted on Edited on In

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

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

先开个线段树的专题吧。

整理了一下模版，快速过了 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 题等下次什么时候想把树链剖分翻出来的时候再研究吧。

Related Posts