分治法求k1到k2

分治法可以用来解决一些区间查询问题，比如求区间第k小。假设我们要求一个数组arr中从k1到k2的数的和，可以按照如下步骤进行分治：

1. 将数组一分为二，得到左半部分left和右半部分right。

2. 如果k2小于等于left的长度，说明要求的区间在left中，递归地对left进行求解即可。

3. 如果k1大于right的长度，说明要求的区间在right中，递归地对right进行求解即可。

4. 否则，我们需要求解的区间跨越了left和right，此时我们需要在left和right中各取前k1和k2-left.length个数进行求和，得到最终结果。

下面是一个Java实现的例子：

public int sumInRange(int[] arr, int k1, int k2) {
    return sumInRangeHelper(arr, k1, k2, 0, arr.length - 1);
}

private int sumInRangeHelper(int[] arr, int k1, int k2, int left, int right) {
    if (left > right) {
        return 0;
    }
    if (k2 <= left + k1 - 1) {
        return sumInRangeHelper(arr, k1, k2, left, left + k1 - 1);
    }
    if (k1 > right - left + 1 - k2 + left) {
        return sumInRangeHelper(arr, k1 - (right - left + 1 - k2 + left), k2 - left, left + k1, right);
    }
    int sum = 0;
    for (int i = left; i <= right; i++) {
        if (i >= left + k1 && i <= left + k2 - 1) {
            sum += arr[i];
        }
    }
    return sum;
}

其中，sumInRange方法是对外暴露的接口，调用sumInRangeHelper方法进行递归求解。sumInRangeHelper方法中，left和right表示当前要求解的区间范围，k1和k2表示要求解的区间在当前区间中的位置，arr是输入的数组。