“二分查找 + （必要时）前缀和” -- 处理 ’有序数组‘ 的区间问题汇总

例题1：
P3184 [USACO16DEC] Counting Haybales S - 洛谷

import sys, bisect# def satisfied(hay):
#     return True if hay in hays else Falsedata = sys.stdin.read().split()
data = iter(data)ans = []
N = int(next(data))
Q = int(next(data))hays = [int(next(data)) for _ in range(N)]
hays.sort() # 2 3 5 7 这样看区间比较直观for _ in range(Q):start = int(next(data))end = int(next(data))# .index() 太慢 -- 线性查找，不适合大数据  --> 建议bisect用于查找第一个target的位置# interval = hays.index(end) - hays.index(start) + 1 # index从0开始，需补1s_index = bisect.bisect_left(hays, start)e_index = bisect.bisect_right(hays, end)interval = e_index - s_index # # index从0开始，需补1ans.append(interval)sys.stdout.write("\n".join(map(str, ans)))

题目1：区间和查询（Range Sum Query）

题目描述：
给定一个已排序的非负整数数组（长度 n），以及 Q 个查询。每个查询给出两个整数 L 和 R（表示数值），要求输出数组中所有落在 [L,R] 内的数的和；如果没有则输出 0。

import sys
import bisect
from itertools import accumulatedef range_sum_query():data = sys.stdin.read().split()it = iter(data)n = int(next(it))q = int(next(it))# 读取数组（题目保证数组已排序，否则需要 sort）arr = [int(next(it)) for _ in range(n)]# 构造前缀和：prefix[i] 表示前 i 个元素的和（prefix[0]=0）prefix = [0] + list(accumulate(arr))out_lines = []for _ in range(q):L = int(next(it))R = int(next(it))# 左边界：第一个不小于 L 的位置left = bisect.bisect_left(arr, L)# 右边界：第一个大于 R 的位置right = bisect.bisect_right(arr, R)sum_val = prefix[right] - prefix[left]out_lines.append(str(sum_val))sys.stdout.write("\n".join(out_lines))if __name__ == '__main__':range_sum_query()

题目2：大于某值的元素计数

题目描述：
给定一个升序排列的数组和 Q个查询。每个查询给定一个整数 X，要求输出数组中大于 X 的元素个数

 

import sys, bisectdef count_greater():data = sys.stdin.read().split()it = iter(data)n = int(next(it))q = int(next(it))arr = [int(next(it)) for _ in range(n)]# 确保数组升序arr.sort()out_lines = []for _ in range(q):X = int(next(it))pos = bisect.bisect_right(arr, X)count = n - posout_lines.append(str(count))sys.stdout.write("\n".join(out_lines))if __name__ == '__main__':count_greater()

题目3：指定区间内的平均值查询

题目描述：
给定一个排序好的数组和 Q 个查询，每个查询给出两个整数 L 和 R，要求计算数组中落在 [L,R] 内所有数的平均值；如果该区间内没有数字，则输出 -1

import sys, bisect
from itertools import accumulatedef interval_average_query():data = sys.stdin.read().split()it = iter(data)n = int(next(it))q = int(next(it))arr = [int(next(it)) for _ in range(n)]# 确保数组升序arr.sort()prefix = [0] + list(accumulate(arr))out_lines = []for _ in range(q):L = int(next(it))R = int(next(it))left = bisect.bisect_left(arr, L)right = bisect.bisect_right(arr, R)count = right - leftif count == 0:out_lines.append("-1")else:sum_val = prefix[right] - prefix[left]avg = sum_val / countout_lines.append(str(avg))sys.stdout.write("\n".join(out_lines))if __name__ == '__main__':interval_average_query()

题目4：“近似”区间计数问题

题目描述：
给定一个升序排列的数组和 Q 个查询。每个查询给定两个整数 XX和 K，要求统计数组中所有与 X 的差值不超过 K 的元素个数，即统计区间 [X−K,X+K] 内的元素个数

import sys, bisectdef approximate_interval_count():data = sys.stdin.read().split()it = iter(data)n = int(next(it))q = int(next(it))arr = [int(next(it)) for _ in range(n)]arr.sort()out_lines = []for _ in range(q):X = int(next(it))K = int(next(it))L = X - KR = X + Kleft = bisect.bisect_left(arr, L)right = bisect.bisect_right(arr, R)count = right - leftout_lines.append(str(count))sys.stdout.write("\n".join(out_lines))if __name__ == '__main__':approximate_interval_count()

题目5：区间频率统计

题目描述：
给定一个升序排列的数组和 Q 个查询，每个查询给定一个目标值 X，要求输出 X 在数组中出现的次数

import sys, bisectdef frequency_count():data = sys.stdin.read().split()it = iter(data)n = int(next(it))q = int(next(it))arr = [int(next(it)) for _ in range(n)]arr.sort()out_lines = []for _ in range(q):X = int(next(it))left = bisect.bisect_left(arr, X)right = bisect.bisect_right(arr, X)count = right - leftout_lines.append(str(count))sys.stdout.write("\n".join(out_lines))if __name__ == '__main__':frequency_count()