HDU-1166 敌兵布阵 (裸线段树算法)

101 阅读 0 评论 67 点赞

我是靠谱客的博主舒心冬日，这篇文章主要介绍HDU-1166 敌兵布阵 (裸线段树算法)，现在分享给大家，希望可以做个参考。

题目大意：

这道题是中文题，也没什么好解释的，就是查询区间内的和，和更新区间内的值。

算法分析：

这道题用我之前接触过的树状数组算法也能做（大概，我对树状数组不是很了解）。我去简单了解了一下线段树，大概就是说，将区间不断一分为二。

比如总共有n个数，第一个节点保存1~n的总值，左孩子保存1 ~ n/2+1区间内的总值，右孩子保存 n/2+1 ~ n 区间内的总值，如此不断迭代下去。

这样的话，无论是更新还是查询，时间复杂度都为logn。

代码实现：

复制代码

#include <stdio.h>
#include <string.h>

#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int value;           // 区间开始
    int begin;           // 区间结束
    int end;
} tree[300000];

int n;
int pa[55000];          // 用于保存每个元素对应的叶子节点

int build(int root, int begin, int end)
{
    tree[root].begin = begin;
    tree[root].end = end;
    if (begin == end) {
        // 因为总是从左孩子开始，所以可以把输入放在初始化线段树的步骤里面
	scanf("%d", &tree[root].value);
        pa[begin] = root;
    } else {
        int left = build(root << 1, begin, begin+(end-begin)/2);
        int right = build(root << 1 | 1, begin+(end-begin)/2+1, end);
        tree[root].value = left + right;
    }
    return tree[root].value;
}

void update(int root, int add)
{
    tree[root].value += add;
    if (root != 1)
        update(root >> 1, add);
}

int query(int root, int front, int rear)
{
    if (front == tree[root].begin && rear == tree[root].end) {      // 函数出口
        return tree[root].value;
    } else if (front > tree[root].end || rear < tree[root].begin) {
        return 0;
    }

int middle = tree[root].begin + (tree[root].end - tree[root].begin) / 2;        // 获取当前范围的终

if (rear < middle) {
        return query(root << 1, front, rear);
    } else if (front > middle+1) {
        return query(root << 1 | 1, front, rear);
    } else {
        int left = query(root << 1, front, middle);
        int right = query(root << 1 | 1, middle+1, rear);
        return left + right;
    }
}

int main()
{
    int times, x, y, add;
    char command[100];

scanf("%d", ×);
    for (int t = 1; t <= times; t++) {
        memset(tree, 0, sizeof(tree));
        scanf("%d", &n);
        tree[0].value = 0;
        build(1, 1, n);
        printf("Case %d:n", t);
        while (scanf("%s", command), strcmp(command, "End")) {
            if (!strcmp(command, "Add")) {
                scanf("%d%d", &x, &add);
                update(pa[x], add);
            } else if (!strcmp(command, "Sub")) {
                scanf("%d%d", &x, &add);
                update(pa[x], -add);
            } else {
                scanf("%d%d", &x, &y);
                printf("%dn", query(1, x, y));
            }
        }
    }

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <string.h>

#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int value;           // 区间开始
    int begin;           // 区间结束
    int end;
} tree[300000];

int n;
int pa[55000];          // 用于保存每个元素对应的叶子节点

int build(int root, int begin, int end)
{
    tree[root].begin = begin;
    tree[root].end = end;
    if (begin == end) {
        // 因为总是从左孩子开始，所以可以把输入放在初始化线段树的步骤里面
	scanf("%d", &tree[root].value);
        pa[begin] = root;
    } else {
        int left = build(root << 1, begin, begin+(end-begin)/2);
        int right = build(root << 1 | 1, begin+(end-begin)/2+1, end);
        tree[root].value = left + right;
    }
    return tree[root].value;
}

void update(int root, int add)
{
    tree[root].value += add;
    if (root != 1)
        update(root >> 1, add);
}

int query(int root, int front, int rear)
{
    if (front == tree[root].begin && rear == tree[root].end) {      // 函数出口
        return tree[root].value;
    } else if (front > tree[root].end || rear < tree[root].begin) {
        return 0;
    }

    int middle = tree[root].begin + (tree[root].end - tree[root].begin) / 2;        // 获取当前范围的终

    if (rear < middle) {
        return query(root << 1, front, rear);
    } else if (front > middle+1) {
        return query(root << 1 | 1, front, rear);
    } else {
        int left = query(root << 1, front, middle);
        int right = query(root << 1 | 1, middle+1, rear);
        return left + right;
    }
}

int main()
{
    int times, x, y, add;
    char command[100];

    scanf("%d", &times);
    for (int t = 1; t <= times; t++) {
        memset(tree, 0, sizeof(tree));
        scanf("%d", &n);
        tree[0].value = 0;
        build(1, 1, n);
        printf("Case %d:n", t);
        while (scanf("%s", command), strcmp(command, "End")) {
            if (!strcmp(command, "Add")) {
                scanf("%d%d", &x, &add);
                update(pa[x], add);
            } else if (!strcmp(command, "Sub")) {
                scanf("%d%d", &x, &add);
                update(pa[x], -add);
            } else {
                scanf("%d%d", &x, &y);
                printf("%dn", query(1, x, y));
            }
        }
    }

    return 0;
}