思路与算法

树状数组维护数列和，把区间开方落实为若干次单点差值更新。0和1开方后不变，用后继并查集记录从某位置起第一个仍可能变化的下标。操作2时只遍历区间内这些活跃下标，计算向下取整平方根并更新差值；新值≤1就把该位置移出活跃集合。操作1照常用前缀之差求和。

正确性说明

每次只跳过已经为0或1的数，它们在今后所有开方操作中都不会变化，所以跳过不影响结果。对其余被访问的位置，更新到精确的整数平方根，并将新旧值之差加入树状数组，从而始终保持树状数组中的和等于真实数列之和。后继结构确保每个尚需改变的位置都被访问，因此所有更新和查询正确。

复杂度

在本题0到10^9范围内，一个数至多成功开方5次便不大于1，所以所有成功修改共 O(N) 次。把这一固定次数视为常数，总时间 O((N+M) log N)，并有近常数的后继查找开销；空间 O(N)。

易错点

本题1查询、2开方，且初始值允许0，不要套用0开方的另一版本。平方根要向下取整，程序会做整数校正。后继查找用迭代路径压缩，避免大量稳定位置组成深链时递归栈溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n + 1), bit(n + 1);
    vector<int> p(n + 2);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    };
    auto add = [&](int u, long long delta) {
        for (; u <= n; u += u & -u)
            bit[u] += delta;
    };
    auto prefix = [&](int u) {
        long long ans = 0;
        for (; u; u -= u & -u)
            ans += bit[u];
        return ans;
    };
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = n; i >= 1; i--)
        if (a[i] <= 1)
            p[i] = find(i + 1);
    int m;
    cin >> m;
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1)
            cout << prefix(r) - prefix(l - 1) << '\n';
        else {
            int i = find(l);
            while (i <= r) {
                long long v = sqrt((long double)a[i]);
                while ((v + 1) * (v + 1) <= a[i])
                    v++;
                while (v * v > a[i])
                    v--;
                add(i, v - a[i]);
                a[i] = v;
                if (v <= 1)
                    p[i] = find(i + 1);
                i = find(i + 1);
            }
        }
    }
}