P4145，50分TLE求调

#include<bits/stdc++.h>

using namespace std;

constexpr int N = 1000005;

long long c[N];

long long n , q , f[N],a[N];

int find(int x){
	return f[x] == x ? x : find(f[x]);
}
void add(int x , int d){
	for(int i = x ; i <= n ; i += i & -i) c[i] += d;
}
long long sum(int x){
	long long ret = 0;
	for(int i = x ; i ; i -= i & -i) ret += c[i];
	return ret;
}
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		long long x;
		cin >> x;
		a[i] = x;
		add(i,x);
		f[i] = i;
	}
	f[n + 1] = n + 1;
	cin >> q;
	for(int i = 1 ; i <= q ; i++){
		long long x , y , z;
		cin >> x >> y >> z;
		if(y > z){
			swap(y , z);
		}
		if(x == 0){
			while(y <= z){
				long long t = sqrt(a[y]);
				add(y , t - a[y]);
				a[y] = t;
				f[y] = a[y]<= 1 ? y + 1 : y;
				y = f[y] == y ? y + 1 : find(f[y]);
			}
		}
		else
		{
			cout << sum(z) - sum(y - 1) << endl;
		}
	}
}