(int jobl, int jobr, int l, int r, int i)
| 52 | // 不用纠结单次调用的复杂度 |
| 53 | // 哪怕调用再多次sqrt方法，总的时间复杂度也就是O(n * 6 * logn) |
| 54 | public static void sqrt(int jobl, int jobr, int l, int r, int i) { |
| 55 | if (l == r) { |
| 56 | long sqrt = (long) Math.sqrt(max[i]); |
| 57 | sum[i] = sqrt; |
| 58 | max[i] = sqrt; |
| 59 | } else { |
| 60 | int mid = (l + r) >> 1; |
| 61 | if (jobl <= mid && max[i << 1] > 1) { |
| 62 | sqrt(jobl, jobr, l, mid, i << 1); |
| 63 | } |
| 64 | if (jobr > mid && max[i << 1 | 1] > 1) { |
| 65 | sqrt(jobl, jobr, mid + 1, r, i << 1 | 1); |
| 66 | } |
| 67 | up(i); |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | // 没有懒更新 |
| 72 | // 不需要调用down方法 |