1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 100006 5 using namespace std; 6 struct data 7 { 8     int l,r; 9     long long zhi;10     bool kg;11 }shu[4*M];12 int n,m;13 void jian(int a1,int l,int r)14 {15     shu[a1].l=l;16     shu[a1].r=r;17     if(l==r)18       {19         scanf("%lld",&shu[a1].zhi);20         if(shu[a1].zhi==1)21           shu[a1].kg=1;22         return;23       }24     int mid=(l+r)>>1;25     jian(a1*2,l,mid);26     jian(a1*2+1,mid+1,r);27     shu[a1].zhi=shu[a1*2].zhi+shu[a1*2+1].zhi;28     shu[a1].kg=shu[a1*2].kg&shu[a1*2+1].kg;29     return;30 }31 void gai(int a1,int l,int r)32 {33     if(shu[a1].kg)34       return;35     if(shu[a1].l==shu[a1].r)36       {37         shu[a1].zhi=floor(sqrt(shu[a1].zhi));38         if(shu[a1].zhi<2)39           shu[a1].kg=1;40         return;41       }42     int mid=(shu[a1].l+shu[a1].r)>>1;43     if(l<=mid)44       gai(a1*2,l,r);45     if(r>mid)46       gai(a1*2+1,l,r);47     shu[a1].zhi=shu[a1*2].zhi+shu[a1*2+1].zhi;48     shu[a1].kg=shu[a1*2].kg&&shu[a1*2+1].kg;49     return;50 }51 long long xun(int a1,int l,int r)52 {53     if(shu[a1].l>=l&&shu[a1].r<=r)54       return shu[a1].zhi;55     long long sum=0;56     int mid=(shu[a1].l+shu[a1].r)>>1;57     if(l<=mid)58       sum+=xun(a1*2,l,r);59     if(r>mid)60       sum+=xun(a1*2+1,l,r);61     return sum;62 }63 int main()64 {65     scanf("%d",&n);66     jian(1,1,n);67     scanf("%d",&m);68     for(int i=1;i<=m;i++)69       {70         int a1,a2,a3;71         scanf("%d%d%d",&a1,&a2,&a3);72         if(a2>a3)73           swap(a2,a3);74         if(a1==2)75           gai(1,a2,a3);76         if(a1==1)77           printf("%lld\n",xun(1,a2,a3));78       }79     return 0;80 }
       
      
     

线段树每次开根号，如果他的所有叶节点都是1，就不用再开了。