首页 > 代码库 > 线段树RMQ
线段树RMQ
水
#include <stdio.h> #include <string.h> #define maxn 1000002 #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 int T[maxn << 2]; int min(int a, int b) { return a < b ? a : b; } void pushUp(int rt) { T[rt] = min(T[rt<<1], T[rt<<1|1]); } void build(int l, int r, int rt) { if(l == r) { scanf("%d", &T[rt]); return; } int mid = (l + r) >> 1; build(lson); build(rson); pushUp(rt); } void update(int pos, int V, int l, int r, int rt) { if(l == r) { T[rt] = V; return; } int mid = (l + r) >> 1; if(pos <= mid) update(pos, V, lson); else update(pos, V, rson); pushUp(rt); } int query(int L, int R, int l, int r, int rt) { if(L == l && R == r) return T[rt]; int mid = (l + r) >> 1; if(R <= mid) return query(L, R, lson); else if(L > mid) return query(L, R, rson); return min(query(L, mid, lson), query(mid + 1, R, rson)); } int main() { int N, i, Q, a, c, b; scanf("%d", &N); build(1, N, 1); scanf("%d", &Q); while(Q--) { scanf("%d%d%d", &c, &a, &b); if(c) update(a, b, 1, N, 1); else printf("%d\n", query(a, b, 1, N, 1)); } return 0; }
线段树RMQ
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。