首先O(n)预处理区间和,这样对每一段区间就可以进行O(1)的询问,很直观的一种方法是二分区间长度,总的时间复杂度是O(nlog(n))

另外不难想要还有O(n)的双指针扫描法。