题目：http://acm.hdu.edu.cn/showproblem.php?pid=4027
数据很大，很容易发现要用线段树，但是在不能建成普通的叶子树，要弄成区间的，成段的更新。那样每次更改节点的复杂度很大。仿造别人的代码才AC掉，
而且if(trie[id].isOne==1) return;写成了if(trie[id].isOne=1) return; 导致查了半天！！
这题的关键题解是 2^64次方 最多开6次平方根就变成1了，所以只要标记节点内的点是否全部为1....不为1继续改变树。
下面是AC代码：
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
#define N 100005
__int64 a[100005];
struct node
{
int l,m,r;
__int64 num;
int isOne;
}trie[N*3];
void creat(int id,int beg,int end)
{
trie[id].l=beg;
trie[id].r=end;
trie[id].isOne=0;
trie[id].m=(beg+end)>>1;
if(beg==end){
if(a[beg]==1)
trie[id].isOne=1;
trie[id].num=a[beg];
return ;
}
else{
creat(id*2,beg,trie[id].m);
creat(id*2+1,trie[id].m+1,end);
trie[id].num=trie[id*2].num+trie[id*2+1].num;
if(trie[id*2].isOne==1&&trie[id*2+1].isOne==1)
trie[id].isOne=1;
}
}
void update(int id,int beg,int end)
{
if(trie[id].isOne==1) return;
if(trie[id].l==trie[id].r)
{
trie[id].num=(__int64)sqrt(double(trie[id].num));
// cout<<trie[id].num<<endl;
if(trie[id].num==1)
trie[id].isOne=1;
return ;
}
else
{
// cout<<434223423<<endl;
if(trie[id].m>=end)
{
update(id*2,beg,end); //在左子树
}
else if(trie[id].m+1<=beg)
{
update(id*2+1,beg,end); //在右子树
}
else{
update(id*2,beg,trie[id].m);
update(id*2+1,trie[id].m+1,end);
}
}
trie[id].num=trie[id*2].num+trie[id*2+1].num;
if(trie[id*2].isOne==1&&trie[id*2+1].isOne==1)
trie[id].isOne=1;
}
__int64 find(int id,int beg,int end)
{
if(trie[id].isOne==1) return end-beg+1;
if(trie[id].l==beg&&trie[id].r==end){
return trie[id].num;
}
else{
if(trie[id].m>=end){
return find(id*2,beg,end);
}
else if(trie[id].m+1<=beg){
return find(id*2+1,beg,end);
}
else
return find(id*2,beg,trie[id].m)+find(id*2+1,trie[id].m+1,end);
}
}
int main(){
int n,m,i,j,t,x,y,temp,ca=1;
while(scanf("%d",&n)!=EOF){
for(i=1;i<=n;i++){
scanf("%I64dd",&a[i]);
}
creat(1,1,n);
scanf("%d",&m);
printf("Case #%d:\n",ca++);
for(i=0;i<m;i++){
scanf("%d%d%d",&t,&x,&y);
if(x>y){
temp=x;
x=y;
y=temp;
}
if(t==0){
update(1,x,y);
}
else{
printf("%I64d\n",find(1,x,y));
}
}
cout<<endl;
}
return 0;
}