【线段树】HDU 1166 敌兵布阵

这道题目是线段树里面最基础的单点更新问题。

设计的知识点包括线段树的单点更新和区间查询。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

G++代码：

#include <cstdio>

#include <string>

using namespace std;

#define lson l, m, rt << 1

#define rson m+1, r, rt << 1 | 1

const int maxn = 50050;

int sum[maxn<<2];

void pushUp(int rt) {

    sum[rt] = sum[rt<<1] + sum[rt<<1|1];

}

void build(int l, int r, int rt) {

    if (l == r) {

        scanf("%d", &sum[rt]);

        return;

    }

    int m = (l + r) >> 1;

    build(lson);

    build(rson);

    pushUp(rt);

}

void update(int p, int add, int l, int r, int rt) {

    if (l == r) {

        sum[rt] += add;

        return;

    }

    int m = (l + r) >> 1;

    if (p <= m) update(p, add, lson);

    else update(p, add, rson);

    pushUp(rt);

}

int query(int L, int R, int l, int r, int rt) {

    if (L <= l && r <= R) {

        return sum[rt];

    }

    int m = (l + r) >> 1;

    int res = 0;

    if (L <= m) res += query(L, R, lson);

    if (R >= m+1) res +=  query(L, R, rson);

    return res;

}

int T, n, cas = 1, a, b;

char s[11];

int main() {

    scanf("%d", &T);

    while (T --) {

        printf("Case %d:\n", cas ++);

        scanf("%d", &n);

        build(1, n, 1);

        while (scanf("%s", s)) {

            if (s[0] == 'Q') {  // Query

                scanf("%d%d", &a, &b);

                printf("%d\n", query(a, b, 1, n, 1));

            } else if (s[0] == 'A') {   // Add

                scanf("%d%d", &a, &b);

                update(a, b, 1, n, 1);

            } else if (s[0] == 'S') {   // Sub

                scanf("%d%d", &a, &b);

                update(a, -b, 1, n, 1);

            } else if (s[0] == 'E') {   // End

                break;

            }

        }

    }

    return 0;

}

巴特西

【线段树】HDU 1166 敌兵布阵

最新文章

热门文章