树状数组单点修改，需要修改的点用 set 维护即可，可以证明修改次数一定不多于 $\text{O}(n \log \log V)$，其中 $V$ 是值域。复杂度不会证，反正不劣于 $\text{O}(n\log^2 n\log \log V+q\log n)$

#include<bits/stdc++.h>
using namespace std;
struct BIT{
    long long a[1000005];
    void update(int x,long long y){
        while(x<1000005)a[x]+=y,x+=(x&-x);
    }
    long long query1(int x){
        long long ans=0;
        while(x)ans+=a[x],x-=(x&-x);
        return ans;
    }
    long long query(int x,int y){
        return query1(y)-query1(x-1);
    }
}b;
set<int>st;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,q;
    cin>>n;
    for(int i=1;i<=n;i++){
        long long a;
        cin>>a;
        b.update(i,a);
        if(a>1)st.insert(i);
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        int op;
        long long x,y;
        cin>>op>>x>>y;
        if(op==1)cout<<b.query(x,y)<<endl;
        else{
            auto l=st.lower_bound(x),r=st.upper_bound(y);
            vector<set<int>::iterator>z;
            for(auto i=l;i!=r;i++){
                auto w=b.query((*i),(*i)),v=(long long)(sqrt(w)+(1e-10))-w;
                b.update((*i),(long long)(sqrt(w)+(1e-10))-w);
                if(w-v<=1)z.push_back(i);
            }
            for(auto i:z)st.erase(i);
        }
    }
    return 0;
}