如何高效实现intervals对应区间内TIME元素的加权求和？

我有三个列表intervals、TIME和list3，需要完成以下操作：

• 遍历intervals中的每个t，定义区间(t - dt/2, t + dt/2)
• 计算TIME中落在该区间内的元素对应的1/list3[n]的总和（n为TIME中符合条件元素的索引）

目前我用以下代码统计符合条件的元素数量，但它无法实现加权求和逻辑，且数据量较大时暴力遍历效率极低，需要更高效的实现方法：

counts = []
for t in intervals:
    # 定义时间区间边界
    lower_bound = t - dt / 2
    upper_bound = t + dt / 2
    # 统计TIME中落在该区间内的元素数量
    count = np.sum(np.logical_and(TIME > lower_bound, TIME < upper_bound)) # 统计True的数量
    counts.append(count)

需求示例 #

当t=1、dt=0.1时，区间为[0.9, 1.1]，若TIME=[0.8,0.9,1.0,1.1,1.2]、list3=[0.1,0.2,0.3,0.4,0.5]，需计算的结果是1/list3[1] + 1/list3[2] + 1/list3[3]，即5 + 3.333... + 2.5 = 10.833...。

高效实现方案 #

暴力遍历的时间复杂度为O(M*N)（M为intervals长度，N为TIME长度），通过排序+二分查找+前缀和可将复杂度降至O(N log N + M log N)，大幅提升效率：

1. 预处理：对TIME排序，同时同步调整list3对应的权重数组（weights = 1/list3），保证时间与权重的对应关系
2. 生成权重的前缀和数组，让区间求和操作变为O(1)
3. 对每个t，用二分查找快速定位区间边界，通过前缀和直接计算区间内的权重和

代码实现

import numpy as np

# 1. 预处理：排序TIME并同步对应权重
sorted_idx = np.argsort(TIME)
sorted_TIME = TIME[sorted_idx]
weights = 1.0 / np.array(list3)
sorted_weights = weights[sorted_idx]

# 2. 生成前缀和数组，prefix_sum[i]表示前i个元素的和
prefix_sum = np.concatenate(([0], np.cumsum(sorted_weights)))

result_sums = []
for t in intervals:
    lower = t - dt / 2
    upper = t + dt / 2
    # 二分查找区间左边界：第一个大于lower的元素索引
    left_pos = np.searchsorted(sorted_TIME, lower, side='right')
    # 二分查找区间右边界：第一个大于等于upper的元素索引
    right_pos = np.searchsorted(sorted_TIME, upper, side='left')
    # 前缀和计算区间权重和
    current_sum = prefix_sum[right_pos] - prefix_sum[left_pos]
    result_sums.append(current_sum)

方案说明

• np.argsort：获取排序后的索引，确保TIME和权重数组的对应关系不被破坏
• np.searchsorted：利用二分查找快速定位区间边界，时间复杂度为O(log N)，远快于遍历整个数组
• 前缀和数组：将区间求和操作从O(k)（k为区间内元素数）降为O(1)，进一步优化性能

内容的提问来源于stack exchange，提问作者Thunder Owl