区间是否奇偶交替：预计算相邻违规边

题意与假设

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

• 整数数组静态不更新；query(left,right)采用闭区间，合法单点恒为True。
• 负数奇偶按mod2定义，与正数规则相同。

解题路线

1. 定义bad[i]为此前若干元素中的同奇偶相邻对累计数，示例bad[t]覆盖右端下标<t的违规边。
2. 区间内部边的右端下标为left+1..right，因此违规数=bad[right+1]−bad[left+1]。等于0则整个区间交替。
3. 前缀明确排除右端left的边，那条边连接的是区间外的left−1。这个下标解释比背差分式更可靠。

手动走一遍

[2,3,5,8]的唯一坏边为3→5，query(0,3)=False；query(2,3)=True，不能把1→2那条外部坏边算进来。query(1,1)=True，没有内部边。

Python 参考实现

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

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

class ParityIndex:
    def __init__(self, a):
        self.n = len(a)
        self.bad = [0] * (self.n + 1)
        for i in range(self.n):
            self.bad[i + 1] = self.bad[i] + (i > 0 and a[i] % 2 == a[i - 1] % 2)

    def query(self, left, right):
        if not 0 <= left <= right < self.n:
            raise ValueError("invalid closed range")
        return self.bad[right + 1] == self.bad[left + 1]

复杂度

建表O(n)时间/空间，每query O(1)；动态更新合同可用Fenwick或segment tree维护两条受影响边。

易错点与追问

容易失分的边界

• 不要按数值差为1判断，这里只要求奇偶不同。
• 错误差分bad[right+1]−bad[left]会包含区间外左边。

继续深挖

• set(index,value)只改变哪些相邻边？
• 如要求相邻差恰为±1，这个边标记方案还能怎样复用？