单点更新 区间查询最值 线段树 杭电hdu1754
初学线段树，觉得线段树美在它的递归实现，可以更新，RMQ算法可以实现区间查询最值，我不知道怎么修改
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 200007; //线段树的节点segTree[i]存根为i的线段树的最值（用RMQ算法不能更新） int segTree[N << 2]; void build(int rt, int l, int r) { if (l == r) { scanf("%d", segTree + rt); return; } int mid = l + r >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); segTree[rt] = max(segTree[rt << 1], segTree[rt << 1 | 1]); } int query(int rt, int l, int r, int L, int R) { //当前根rt在区间[l,r],所查询区间为[L,R] if (L <= l && r <= R) return segTree[rt]; int mid = l + r >> 1, Max = 0; if (L <= mid) Max = max(Max, query(rt << 1, l, mid, L, R)); if (R > mid) Max = max(Max, query(rt << 1 | 1, mid + 1, r, L, R)); return Max; } void update(int rt, int l, int r, int pos, int val) { //当前rt所在区间为[l,r],把原始数据中第pos个数改为val if (l == r) { segTree[rt] = val; return; } int mid = l + r >> 1; if (pos <= mid) update(rt << 1, l, mid, pos, val); else update(rt << 1 | 1, mid + 1, r, pos, val); segTree[rt] = max(segTree[rt << 1], segTree[rt << 1 | 1]); //别忘了回溯 } int main() { int n, m; while (~scanf("%d%d", &n, &m)) { memset(segTree, 0, sizeof segTree); build(1, 1, n); while (m-- > 0) { char opt; int a, b; scanf(" %c%d%d", &opt, &a, &b); if (opt == 'Q') printf("%d\n", query(1, 1, n, a, b)); else if (opt == 'U') update(1, 1, n, a, b); } } return 0; }
附线段树题 hdu 2795
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 200007; int segTree[N << 2]; //segTree[i]保存节点i所在线段树的可利用的行宽的最大值 int h, w, n; void build(int rt, int l, int r) { segTree[rt] = w; if (l == r) return; int mid = l + r >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); } int query(int rt, int l, int r, int x) { if (l == r) { segTree[rt] -= x;//查询时更新了 return l; } int mid = l + r >> 1, res; if (segTree[rt << 1] >= x) res = query(rt << 1, l, mid, x); else res = query(rt << 1 | 1, mid + 1, r, x); segTree[rt] = max(segTree[rt << 1], segTree[rt << 1 | 1]); return res; } int main() { while (~scanf("%d%d%d", &h, &w, &n)) { memset(segTree, 0, sizeof segTree); h = min(h, n); //板子行数多于信息条数的用不到 build(1, 1, h); while (n-- > 0) { int x; scanf("%d", &x); if (segTree[1] < x) puts("-1"); else printf("%d\n", query(1, 1, h, x)); } } return 0; }
