首页 > 代码库 > HDU 1754 I hate it 分段树Segment Tree题解
HDU 1754 I hate it 分段树Segment Tree题解
给出一段数据,然后要更新单个数据,会询问一段数据中的最大值。
又是一道分段树操作。渐渐熟手了。
#pragma once #include <cstdio> #include <algorithm> using namespace std; class IHateIt_1754_1 { static const int SIZE = 200001; int *segTree; //不要使用segTree[SIZE<<2] inline int lChild(int r) { return r<<1; } inline int rChild(int r) { return r<<1|1; } void pushUp(int rt) { segTree[rt] = max(segTree[lChild(rt)], segTree[rChild(rt)]); } void build(int l, int r, int rt) { if (l == r) { scanf("%d", &segTree[rt]); return ; } int m = l + ((r-l)>>1); build(l, m, lChild(rt)); build(m+1, r, rChild(rt)); pushUp(rt); } void update(const int stu, const int score, int l, int r, int rt) { if (l == r) { segTree[rt] = score; return ; } int m = l + ((r-l)>>1); if (stu <= m) update(stu, score, l, m, lChild(rt)); else update(stu, score, m+1, r, rChild(rt)); pushUp(rt); } int query(const int L, const int R, int l, int r, int rt) { if (L <= l && r <= R) return segTree[rt]; int m = l + ((r-l)>>1); int res = 0; if (L <= m) res = query(L, R, l, m, lChild(rt));//注意下标 if (R > m) res = max(res, query(L, R, m+1, r, rChild(rt))); return res; } public: IHateIt_1754_1() : segTree((int *) malloc (sizeof(int) * (SIZE<<2))) { int N, M; while (scanf("%d %d", &N, &M) != EOF) { build(1, N, 1); while (M--) { char op[2]; int a, b; scanf("%s%d%d", op, &a, &b); if (op[0] == 'U') update(a, b, 1, N, 1); else printf("%d\n",query(a, b, 1, N, 1)); } } } ~IHateIt_1754_1() { if (segTree) free(segTree); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。