Class Code03_SquareRoot

src/class111/Code03_SquareRoot.java:21–124

import java.io.StreamTokenizer;

public class Code03_SquareRoot {

	public static int MAXN = 100001;

	public static long[] arr = new long[MAXN];

	public static long[] sum = new long[MAXN << 2];

	public static long[] max = new long[MAXN << 2];

	public static void up(int i) {
		sum[i] = sum[i << 1] + sum[i << 1 | 1];
		max[i] = Math.max(max[i << 1], max[i << 1 | 1]);
	}

	public static void build(int l, int r, int i) {
		if (l == r) {
			sum[i] = arr[l];
			max[i] = arr[l];
		} else {
			int mid = (l + r) >> 1;
			build(l, mid, i << 1);
			build(mid + 1, r, i << 1 | 1);
			up(i);
		}
	}

	// sqrt方法是最核心的
	// 注意和常规线段树不一样，这里没有懒更新，也就不需要有down方法
	// 只有根据范围最大值信息的剪枝
	// 时间复杂度的分析就是课上讲的势能分析
	// 不用纠结单次调用的复杂度
	// 哪怕调用再多次sqrt方法，总的时间复杂度也就是O(n * 6 * logn)
	public static void sqrt(int jobl, int jobr, int l, int r, int i) {
		if (l == r) {
			long sqrt = (long) Math.sqrt(max[i]);
			sum[i] = sqrt;
			max[i] = sqrt;
		} else {
			int mid = (l + r) >> 1;
			if (jobl <= mid && max[i << 1] > 1) {
				sqrt(jobl, jobr, l, mid, i << 1);
			}
			if (jobr > mid && max[i << 1 | 1] > 1) {
				sqrt(jobl, jobr, mid + 1, r, i << 1 | 1);
			}
			up(i);
		}
	}

	// 没有懒更新
	// 不需要调用down方法
	public static long query(int jobl, int jobr, int l, int r, int i) {
		if (jobl <= l && r <= jobr) {
			return sum[i];
		}
		int mid = (l + r) >> 1;
		long ans = 0;