HDOJ 1754
线段树裸题，直接上代码。
AC code：
递归线段树：
//lrl's submission #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define debug 0 #define ls root << 1, l, mid #define rs root << 1 | 1, mid + 1, r #define M(a, b) memset(a, b, sizeof(a)) const int maxn = 200000 + 5; int mx[maxn << 2], n, m, ip = 0; void pushUp(int root){ mx[root] = max(mx[root << 1], mx[root << 1|1]); } void build(int root, int l, int r){ if(l == r){ scanf("%d", &mx[root]); return; } //printf("%d %d\n", l, r); //ip++; //if(ip == 6) //return; //return; int mid = (l + r) >> 1; build(ls); build(rs); pushUp(root); } void update(int root, int l, int r, int a, int b){ if(l == r){ if(l == a){ mx[root] = b; } return; } if(a < l || a > r) return; int mid = (l + r) >> 1; update(ls, a, b); update(rs, a, b); pushUp(root); } int query(int root, int l, int r, int a, int b){ if(b < l || a > r) return 0; if(a <= l && r <= b) return mx[root]; int mid = (l + r) >> 1; return max(query(ls, a, b), query(rs, a, b)); } int main() { #if debug freopen("in.txt", "r", stdin); #endif // debug char s[5]; int a, b; while(~scanf("%d%d", &n, &m)) { //printf("%d %d\n", n, m); M(mx, 0); build(1, 1, n); while(m--) { scanf("%s%d%d", s, &a, &b); //printf("%d %d\n", a, b); if(s[0] == 'Q'){ printf("%d\n", query(1, 1, n, a, b)); } else{ update(1, 1, n, a, b); } } } return 0; } 写宏的时候， 括号一定要注意， 刚开始mid用宏写没套括号。。。。
zkw线段树， 简单多了：
//lrl's submission #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define debug 0 #define mid (l + r) >> 1 #define ls root << 1, l, mid #define rs root << 1 | 1, mid + 1, r #define M(a, b) memset(a, b, sizeof(a)) const int maxn = 200000 + 5; int mx[maxn << 2], n, m, M; void build() { for(M = 1; M <= n + 1; M <<= 1); for(int i = M + 1; i <= M + n; i++){ scanf("%d", &mx[i]); } for(int i = M - 1; i >= 1; i--) mx[i] = max(mx[i << 1], mx[i << 1|1]); } void update(int a, int b){ for(mx[a += M] = b, a >>= 1; a; a >>= 1) mx[a] = max(mx[a << 1], mx[a << 1|1]); } int query(int a, int b){ a += M - 1; b += M + 1; int ans = 0; while(b - a > 1){ if(a % 2 == 0){ ans = max(ans, mx[a + 1]); } if(b % 2) ans = max(ans, mx[b - 1]); a >>= 1; b >>= 1; } return ans; } int main() { #if debug freopen("in.txt", "r", stdin); #endif // debug char s[5]; int a, b; while(~scanf("%d%d", &n, &m)) { //printf("%d %d\n", n, m); M(mx, 0); build(); while(m--) { scanf("%s%d%d", s, &a, &b); //printf("%d %d\n", a, b); if(s[0] == 'Q'){ printf("%d\n", query(a, b)); } else{ update(a, b); } } } return 0; }
