Meta 动态两数组和：更新secondary与统计下标对

题意与假设

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

• primary固定，secondary更新是赋新val而非加val；所有合法(i,j)按下标分别计数。
• 示例类提供update(index,value)/query(target)，正式operations编码在外层解析；越界拒绝且状态不应改变。

解题路线

1. 用Counter记录primary与secondary值频次。赋值前先减少旧值计数，0则删键，再增加新值；同时更新secondary数组供下次找到旧值。
2. 查询遍历primary不同值v，贡献primaryCount[v]×secondaryCount[target−v]。不用把每个重复primary值重复查一遍，更不能set去重后丢乘法贡献。
3. 预计算全部pairSum可使query O(1)，但每次secondary更新要对每个primary不同值修正旧sum/新sum，且sum种类可能很大；read heavy与write heavy决定选型。

手动走一遍

primary=[1,1,2]，secondary=[2,3]，query4有两个1+3以及一个2+2，共3。将secondary[0]赋3后，query4有四个1+3，共4。

Python 参考实现

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

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

from collections import Counter


class PairSumCounter:
    def __init__(self, primary, secondary):
        self.primary = Counter(primary)
        self.secondary = list(secondary)
        self.frequency = Counter(secondary)

    def update(self, index, value):
        if not 0 <= index < len(self.secondary):
            raise IndexError("secondary index outside array")
        old = self.secondary[index]
        self.frequency[old] -= 1
        if self.frequency[old] == 0:
            del self.frequency[old]
        self.secondary[index] = value
        self.frequency[value] += 1

    def query(self, target):
        return sum(count * self.frequency.get(target-value,0) for value,count in self.primary.items())

复杂度

预处理O(n+m)，update预期O(1)，query O(U_primary)；空间O(m+U_primary+U_secondary)。预计算sum索引的大小最坏O(U_primary×U_secondary)。

易错点与追问

容易失分的边界

• 只用set只能知道值存在，无法统计重复下标pairs。
• 把更新当increment会在多次操作后偏离要求。

继续深挖

• 两个数组都可更新时维护两边Counter，查询遍历不同值更少的一边。
• 若pairCount要支持并发强一致，update数组与freq同一事务/锁，查询需要一致快照。