題意：給定100000個數，兩種操作，0 i j表示將i j這段的數字都開根號（向下取整），1 i j表示查詢i j之間的所有值的和。。。（所有的和都不超過64位）

解題思路：這題要做區間的開平方操作，2^64最多可以做8次開平方操作，所以對于每個節點最多只有8次操作，這道題如果lazy思想的話就要保存每個區間被開平方的次數，但實際上好像不需要，只要一直找到葉子節點并將其開平方即可。如果整個區間內的數都為1，那么就直接返回即可，不需要再往下遞歸了。

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; typedef long long LL; const int maxn = 100010;LL sum[maxn*4]; int n, m;void PushUp(int rt) {sum[rt] = sum[rt<<1] + sum[rt<<1|1];return ; }void build(int l, int r, int rt) {sum[rt] = 0;if(l == r){scanf("%I64d", &sum[rt]);return ;}int m = (l+r)>>1;build(lson);build(rson);PushUp(rt); }void update(int L, int R, int l, int r, int rt) {if(l == r){sum[rt] = sqrt(1.0 * sum[rt]);return ;}if(L<=l && r<=R && sum[rt]==r-l+1) return ;int m = (l + r)>>1;if(L <= m) update(L, R, lson);if(m < R) update(L, R, rson);PushUp(rt); }LL query(int L, int R, int l, int r, int rt) {if(L <= l && r <= R)return sum[rt];int m = (l + r)>>1;LL ans = 0;if(L <= m) ans += query(L, R, lson);if(m < R) ans += query(L, R, rson);return ans; }int main() {int test = 0;while(scanf("%d", &n) != EOF){build(1, n, 1);int a, b, c;int x, y;scanf("%d", &m);printf("Case #%d:\n", ++test);while(m--){scanf("%d%d%d", &a, &b, &c);x = min(b, c);y = max(b, c);if(a == 0){update(x, y, 1, n, 1);}else{printf("%I64d\n", query(x, y, 1, n, 1));}}puts("");}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4027（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。