本文主要是介绍hdu 1166 敌兵布阵（树状数组 or 线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是求一个线段的和，在线段上可以进行加减的修改。
树状数组的模板题。
代码：
#include <stdio.h>
#include <string.h>
const int maxn = 50000 + 1;int c[maxn];
int n;int lowbit(int x)
{return x & -x;
}void add(int x, int num)
{while (x <= n){c[x] += num;x += lowbit(x);}
}void sub(int x, int num)
{while (x <= n){c[x] -= num;x += lowbit(x);}
}int query(int x)
{int res = 0;while (x > 0){res += c[x];x -= lowbit(x);}return res;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALint ncase;scanf("%d", &ncase);for (int t = 1; t <= ncase; t++){memset(c, 0, sizeof(c));scanf("%d", &n);for (int i = 1; i <= n; i++){int tmp;scanf("%d", &tmp);add(i, tmp);}char ch[6];printf("Case %d:\n", t);while (1){scanf("%s", ch);getchar();if (strcmp(ch, "Query") == 0){int from, to;scanf("%d%d", &from, &to);printf("%d\n", query(to) - query(from - 1));continue;}if (strcmp(ch, "Add") == 0){int x, num;scanf("%d%d", &x, &num);add(x, num);continue;}if (strcmp(ch, "Sub") == 0){int x, num;scanf("%d%d", &x, &num);sub(x, num);continue;}if (strcmp(ch, "End") == 0){break;}}}return 0;
}
2015.4.20
线段树：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1
const int maxn = 50000 + 10;LL sum[maxn << 2];void pushup(int rt)
{sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}void build(int lo, int hi, int rt)
{if (lo == hi){scanf("%d", &sum[rt]);return;}int mi = (lo + hi) >> 1;build(lson);build(rson);pushup(rt);
}void update(int pos, int add, int lo, int hi, int rt)
{if (lo == hi){sum[rt] += add;return;}int mi = (lo + hi) >> 1;if (pos <= mi)update(pos, add, lson);elseupdate(pos, add, rson);pushup(rt);
}LL query(int L, int H, int lo, int hi, int rt)
{if (L <= lo && hi <= H)return sum[rt];int mi = (lo + hi) >> 1;int res = 0;if (L <= mi)res += query(L, H, lson);if (mi < H)res += query(L, H, rson);return res;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALint ncase;scanf("%d", &ncase);for (int t = 1; t <= ncase; t++){int n;scanf("%d", &n);build(1, n, 1);char ch[6];printf("Case %d:\n", t);while (1){scanf("%s", ch);getchar();if (strcmp(ch, "Query") == 0){int from, to;scanf("%d%d", &from, &to);printf("%d\n", query(from, to, 1, n, 1));continue;}if (strcmp(ch, "Add") == 0){int x, num;scanf("%d%d", &x, &num);update(x, num, 1, n, 1);continue;}if (strcmp(ch, "Sub") == 0){int x, num;scanf("%d%d", &x, &num);update(x, -num, 1, n, 1);continue;}if (strcmp(ch, "End") == 0){break;}}}return 0;
}
这篇关于hdu 1166 敌兵布阵（树状数组 or 线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
