首先，单点修改求区间和可以用树状数组实现
因为开平方很耗时间，所以在这个方面可以优化
我们知道，开平方开几次之后数字就会等于1
所以，用数组记录下一个应该开的数，每次直接跳到下一个不是1的数字进行开平方，至于这个数组，可以用并查集维护。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;typedef long long LL;#define lowbit(x) (x&(-x))
#define N 100010int n,m;
int ask,l,r,t;int f[N],a[N];
LL c[N];inline int getint()
{int x=0,f=1;char ch=getchar();while (ch>'9' || ch<'0'){if (ch=='-')f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}inline int find(int x)
{return x==f[x] ? x : f[x]=find(f[x]);
}inline void add(int x,int d)
{while (x<=n)c[x]+=d,x+=lowbit(x);
}inline LL query(int x)
{LL res(0);while (x)res+=c[x],x-=lowbit(x);return res;
}int main()
{n=getint();for (int i=1;i<=n;i++){a[i]=getint();f[i]=i;add(i,a[i]);}f[n+1]=n+1;m=getint();while (m--){ask=getint(),l=getint(),r=getint();if (ask==1)printf("%lld\n",query(r)-query(l-1));elsefor (int i=l;i<=r;add(i,(t=(int)sqrt(a[i]))-a[i]),a[i]=t,f[i]=(a[i]<=1) ? i+1 : i,i=(find(i)==i ? i+1 : f[i]));}return 0;
}