滑窗去掉最大K项后的平均：计数树与秩前缀和

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 整数数组、窗口W>0、0≤K<W；只对完整窗口输出。
• 示例是已知全数组的离线坐标压缩Fenwick；真正未知值流需有序树或其他在线结构，不能提前压缩未来值。

解题路线

1. 值压缩后，两棵Fenwick分别存次数和数值和。窗口加入/过期各点更新；要去最大K，等价取最小W−K个的和。
2. Fenwick binary lifting找累计次数不超过目标的最后完整值桶，累积这些桶sum；剩余数量在下一个值桶按value×剩数补足，正确处理重复边界。
3. 均值返回Fraction避免浮点；输入是实数时要改数值表示并考虑累积误差。线上平衡多重集合可分低W−K/高K两组，维护低组sum与数量不变量。

手动走一遍

W3,K1窗口[2,5,5]删除一个5，均值(2+5)/2=7/2；不能删掉全部等于最大值的项。窗口全负[−5,−2,−1]删最大−1，剩均值−7/2。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from fractions import Fraction


def trimmed_average(a,width,k):
    if width<=0 or not 0<=k<width:raise ValueError("positive width and 0<=k<width required")
    values=sorted(set(a));rank={x:i+1 for i,x in enumerate(values)};d=len(values)
    count=[0]*(d+1);sums=[0]*(d+1)
    def update(x,delta):
        i=rank[x]
        while i<=d:count[i]+=delta;sums[i]+=delta*x;i+=i&-i
    def smallest_sum(amount):
        i=used=total=0;step=1<<(d.bit_length()-1) if d else 0
        while step:
            j=i+step
            if j<=d and used+count[j]<=amount:i=j;used+=count[j];total+=sums[j]
            step>>=1
        return total+(amount-used)*values[i] if used<amount else total
    result=[]
    for i,x in enumerate(a):
        update(x,1)
        if i>=width:update(a[i-width],-1)
        if i+1>=width:result.append(Fraction(smallest_sum(width-k),width-k))
    return result

复杂度

压缩O(nlogn)，滑动O(nlogd)，空间O(d+n)含输出/全输入，d不同值数。未压缩未知流不能直接沿用此内存界。

易错点与追问

容易失分的边界

• k=W会分母0，必须拒绝或给另一个空均值合同。
• 只维护一堆最大值而不支持过期删除，会累积旧窗口元素。

继续深挖

• 若同时去最大K和最小L，如何用两次秩前缀和计算？
• 在线未知值且高重复时如何维护两组及lazy删除版本？