仿照题解思路写的，能过样例，有大佬能帮蒟蒻调一下吗 QAQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e5+10;

int n, m;
int a[N], p[N], s[N]; //p存储每个点的祖先,s为树状数组

int find(int x) { //路径压缩 
    if (p[x] != x)
        p[x] = find(p[x]); 
    return p[x]; 
} 

int lowbit(int x) {
	return x & -x;
}

void add(int l, int x) { //单点修改 
	for (int i = l; i <= n; i += lowbit(i)) s[i] += x;
}

int query(int l) { //前缀和 
	int sum = 0;
	for (int i = l; i > 0; i -= lowbit(i)) sum += s[i];
	return sum;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		add(i, a[i]);
		p[i] = i;
	}
	p[n+1] = n+1;
	
	scanf("%d", &m);
	while (m -- ) {
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if (l > r) swap(l, r);
		
		if (op) printf("%d\n", query(r)-query(l-1));
		else {
			int i = l;
			while (i <= r) {
				if (p[i] == i) {
					int t = sqrt(a[i]); //s需要减少a[i]-t
					add(i, t-a[i]); a[i] = t; //相当于加上t-a[i]
				 	p[i] = (a[i] == 1) ? i+1 : i;
				 	i = (p[i] == i) ? i+1 : find(p[i]);
				}
			}
		}
	}
	
	return 0;
}