[面试题] 线段树实战：Python实现区间翻转与求和高频面试题

最近一个关于“36岁程序员面试”的话题引发了讨论。抛开对年龄与潜力的争议，回归技术本质，扎实的算法功底始终是程序员的核心竞争力。本文将解析一道能体现算法设计与工程实现能力的经典面试题，并给出高效的Python解决方案。

面试题解析：性别队列的区间操作

题目可以抽象为：一个由'M'(男)和'F'(女)组成的序列，需要高效处理两种操作：

1. C l r：将区间 [l, r] 内所有角色的性别翻转（男变女，女变男）。
2. Q l r：查询区间 [l, r] 内男性（'M'）的数量。

数据规模：序列长度 n 和操作次数 q 均可达到 10^5 级别。这就要求算法必须远优于 O(n*q) 的暴力方法。

暴力解法为何不可行？

最直观的做法是使用数组存储，每次修改遍历区间(O(n))，每次查询也遍历区间(O(n))。在10^5的数据规模下，最坏时间复杂度O(n*q)将高达10^10，必然超时。问题的核心在于：如何同时支持高效的区间修改与区间查询。

问题转化与建模

首先，将性别数字化以便于计算：

• 1 代表男性 ('M')
• 0 代表女性 ('F')

如此，查询区间内男性数量就转化为计算该区间的和。区间翻转操作则意味着：

• 该区间内所有的 1 变为 0
• 所有的 0 变为 1

对于一个长度为 len，原男性数量为 sum 的区间，翻转后新的男性数量为 len - sum。这一转化是设计高效算法的关键。

解决方案：线段树 + 懒标记

这是一个标准的区间修改（翻转）与区间查询（求和）问题。线段树能在 O(log n) 时间内完成这两种操作，是解决此类问题的经典数据结构。为了高效处理区间翻转，需要引入懒惰标记来延迟对子节点的更新。

线段树节点设计：
每个节点代表一个区间 [l, r]，维护两个信息：

1. sum：该区间内男性（1）的数量。
2. lazy_flip：一个布尔标记，表示该区间需要被翻转但尚未传递给子节点。

核心操作逻辑：

1. 区间翻转 (update_range_flip)：当需要翻转一个完全被覆盖的节点区间时，直接更新该节点：sum = (r - l + 1) - sum，并将 lazy_flip 标记取反（^= 1）。
2. 标记下传 (_push_down)：在需要访问或修改当前节点的子节点之前，如果 lazy_flip 为真，则将翻转操作应用到左右子节点，并清空当前节点的标记。
3. 区间查询 (query_range_sum)：查询过程中同样需要先下传懒标记，确保数据的正确性，然后合并子区间的结果。

下面给出完整的Python实现，适用于ACM风格的输入输出。

import sys
sys.setrecursionlimit(1_000_000)

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        # 开 4n 空间
        self.sum = [0] * (4 * self.n)  # 区间和 (男生数)
        self.lazy = [0] * (4 * self.n) # 懒标记：是否需要翻转
        self._build(1, 1, self.n, arr)

    def _build(self, idx, l, r, arr):
        """建树"""
        if l == r:
            self.sum[idx] = arr[l - 1]  # arr 是 0-based
            return
        mid = (l + r) // 2
        self._build(idx * 2, l, mid, arr)
        self._build(idx * 2 + 1, mid + 1, r, arr)
        self._push_up(idx)

    def _push_up(self, idx):
        """用子节点更新父节点和"""
        self.sum[idx] = self.sum[idx * 2] + self.sum[idx * 2 + 1]

    def _apply_flip(self, idx, l, r):
        """对当前节点代表的整个区间应用翻转"""
        length = r - l + 1
        self.sum[idx] = length - self.sum[idx]  # 核心公式
        self.lazy[idx] ^= 1  # 翻转标记

    def _push_down(self, idx, l, r):
        """将当前节点的懒标记下传给子节点"""
        if self.lazy[idx] == 0:
            return
        mid = (l + r) // 2
        # 更新左孩子
        self._apply_flip(idx * 2, l, mid)
        # 更新右孩子
        self._apply_flip(idx * 2 + 1, mid + 1, r)
        # 清除当前标记
        self.lazy[idx] = 0

    def update_range_flip(self, ql, qr, idx=1, l=1, r=None):
        """区间翻转"""
        if r is None:
            r = self.n
        # 区间不相交
        if qr < l or ql > r:
            return
        # 当前区间完全被覆盖
        if ql <= l and r <= qr:
            self._apply_flip(idx, l, r)
            return
        # 部分覆盖，需要下传标记后递归
        self._push_down(idx, l, r)
        mid = (l + r) // 2
        self.update_range_flip(ql, qr, idx * 2, l, mid)
        self.update_range_flip(ql, qr, idx * 2 + 1, mid + 1, r)
        self._push_up(idx)

    def query_range_sum(self, ql, qr, idx=1, l=1, r=None):
        """区间求和 (查询男生数)"""
        if r is None:
            r = self.n
        if qr < l or ql > r:
            return 0
        if ql <= l and r <= qr:
            return self.sum[idx]
        self._push_down(idx, l, r)
        mid = (l + r) // 2
        left_sum = self.query_range_sum(ql, qr, idx * 2, l, mid)
        right_sum = self.query_range_sum(ql, qr, idx * 2 + 1, mid + 1, r)
        return left_sum + right_sum

def main():
    input = sys.stdin.readline
    n, q = map(int, input().split())
    s = input().strip()  # 性别序列，如 "MFMFFM"
    # 转换为 0/1 数组，男=1，女=0
    arr = [1 if ch == 'M' else 0 for ch in s]
    seg = SegmentTree(arr)
    output = []
    for _ in range(q):
        op, l_str, r_str = input().split()
        l, r = int(l_str), int(r_str)
        if op == 'C':
            seg.update_range_flip(l, r)
        elif op == 'Q':
            res = seg.query_range_sum(l, r)
            output.append(str(res))
    sys.stdout.write("\n".join(output))

if __name__ == "__main__":
    main()

算法总结

本题的解决路径清晰体现了从问题抽象到算法设计与优化的完整思维过程：

1. 问题转化：将性别字符映射为 0/1，把性别统计转化为区间求和。
2. 操作分析：发现区间翻转的核心性质是 sum -> len - sum。
3. 数据结构选择：针对10^5级别的区间修改与查询，选择 O(log n) 的线段树。
4. 效率优化：引入懒标记延迟更新，避免不必要的遍历，这是保证高性能系统在处理大规模数据时的关键技巧。

掌握此类问题的解法，不仅能应对面试，更能深刻理解如何利用合适的数据结构来解决实际的工程问题。若想查询单个同学的性别，只需查询单点 Q x x，根据返回的 1 或 0 输出即可。