xml天气预报网站怎么做/北京网聘咨询有限公司

http://acm.hdu.edu.cn/showproblem.php?pid=1166

此题考查RSQ(Range Sum Query)。

线段树：

/*343ms,744KB*//*
我们使用如下缩写：root--整棵树的根节点
rt--当前区间的根节点
l,r--区间左右端点
m--区间的二等分点，注意m是落在左子区间的(右端点)
lson,rson--左右子区间p--position，待更新的位置
ql,qr--待查询区间的左右端点
*/#include <cstdio>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 1, n, 1
const int mx = 50000;int sum[mx << 2];/*
收集当前节点的左右子区间的信息
在递归函数向上返回之前被调用
故称之为pushup
*/
inline 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 addval, int l, int r, int rt)
{if (l == r){sum[rt] += addval;return;}int m = (l + r) >> 1;if (p <= m) update(p, addval, lson);else update(p, addval, rson);pushup(rt);
}/*
二分查找要计算的区间
返回：区间[ql,qr]的查找结果
*/
int query(int ql, int qr, int l, int r, int rt)
{if (ql <= l && r <= qr){return sum[rt];}int sum = 0, m = (l + r) >> 1;if (ql <= m) sum += query(ql, qr, lson);if (m < qr) sum += query(ql, qr, rson);return sum;
}int main()
{int t, i, n, a, b;char s[10];scanf("%d", &t);for (i = 1; i <= t; ++i){printf("Case %d:\n", i);scanf("%d", &n);build(root);while (scanf("%s", s), s[0] != 'E'){scanf("%d%d", &a, &b);if (s[0] == 'A') update(a, b, root);else if (s[0] == 'S') update(a, -b, root);else printf("%d\n", query(a, b, root));}}return 0;
}

树状数组：（速度挺快）

/*140ms,444KB*/#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>int N, r[50001];void update(int p, int m) {while (p <= N) {r[p] += m;p += p & -p;}
}int sum(int n) {int sum = 0;while (n) {sum += r[n];n -= n & -n;}return sum;
}int query(int sta, int end) {return sum(end) - sum(sta - 1);
}int main() {int T;scanf("%d", &T);bool pos = true; //pos用来标示是否输出 Case i:for (int i = 1; i <= T; ++i) {memset(r, 0, sizeof(r));scanf("%d", &N);for (int j = 1; j <= N; ++j) {int add;scanf("%d", &add);update(j, add);}char dos[10];int a, b;while (true) {scanf("%s", dos);if (dos[0] == 'E') {pos = true;break;}scanf("%d%d", &a, &b);if (dos[0] == 'Q') {if (pos) {printf("Case %d:\n", i);pos = false;}printf("%d\n", query(a, b));}elsedos[0] == 'A' ? update(a, b) : update(a, -b);}}return 0;
}