树状数组模板题。注意优化，假设某个数的值已经是1了的话。那么我们以后就不用对他进行操作了，这个能够用并查集实现。
这道题还有个坑的地方，给出查询区间端点的a,b，有可能a>b。
#include<cstdio>
#include<cmath>
#include<cctype>
#include<iostream>
using namespace std;
inline void GET(int &t){
char c;
t=0;
do{c=getchar();}while(!isdigit(c));
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
}
inline void GET(long long &t){
char c;
t=0;
do{c=getchar();}while(!isdigit(c));
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
}
long long tree[100005],c[100005];
int fa[100005];
int n,m;
int root(int x)
{
if(fa[x]==x)
return x;
else
return fa[x]=root(fa[x]);
}
int lowbit(long long x)
{
return x&-x;
}
void updata(int pos,long long val)
{
while(pos<=n)
{
tree[pos]+=val;
pos+=lowbit(pos);
}
}
long long getsum(int pos)
{
long long sum=0;
while(pos>0)
{
sum+=tree[pos];
pos-=lowbit(pos);
}
return sum;
}
int main()
{
GET(n);
for(int i=1;i<=n;i++)
{
GET(c[i]);
updata(i,c[i]);
fa[i]=i;
}
GET(m);
int k,l,r;
for(int i=1;i<=m;i++)
{
GET(k);
GET(l);
GET(r);
if(r < l) swap(l,r);
if(k==1)
printf("%lld
",getsum(r)-getsum(l-1));
else
{
for(int j=root(l);j<=r;j=root(j+1))
{
if(j==0)
break;
updata(j,-c[j]);
c[j]=sqrt(c[j]);
updata(j,c[j]);
if(c[j]==1)
fa[j]=j+1;
}
}
}
}