这道题我刚开始打算是进行区间更新，但是发现不会维护开方，后来发现原来这道题是单点更新，因为开方几次后基本上就变成了1，这样我们只需要对一段区间都是1的情况直接返回
就能降低复杂度
#include<iostream> #include<map> #include<cstdio> #include<vector> #include<cstring> #include<cmath> #include<algorithm> #include<algorithm> using namespace std; typedef long long ll; const int N=5e5+10; const int inf=0x3f3f3f3f; struct node{ int l,r; ll sum; }tr[N<<2]; ll a[N]; void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,a[l]}; } else{ tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void modify(int u,int l,int r){ if(tr[u].l==tr[u].r){ tr[u].sum=sqrt(tr[u].sum); return ; } if(tr[u].sum==tr[u].r-tr[u].l+1) return ; int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,r); if(r>mid) modify(u<<1|1,l,r); pushup(u); } ll query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; int mid=tr[u].l+tr[u].r>>1; ll res=0; if(l<=mid) res+=query(u<<1,l,r); if(r>mid) res+=query(u<<1|1,l,r); return res; } int main(){ int n; int cnt=1; while(cin>>n){ int i; for(i=1;i<=n;i++){ scanf("%lld",&a[i]); } build(1,1,n); printf("Case #%d: ",cnt++); int m; cin>>m; while(m--){ int t; int x,y; scanf("%d%d%d",&t,&x,&y); if(x>y) swap(x,y); if(t==0){ modify(1,x,y); } else{ printf("%lld ",query(1,x,y)); } } cout<<endl; } }