线段树的区间众数查询与更新操作详解

1. 问题描述

区间众数查询是这样一个问题：给定一个长度为n的数组，需要支持两种操作：

1. 查询操作：查询区间[L, R]内的众数（出现次数最多的元素）
2. 更新操作：将某个位置的值修改为新的值

注意：这里我们讨论的是在线段树上实现区间众数查询，这是一个相对高级的应用场景，因为众数不满足区间可加性（即知道左右子区间的众数，不能直接推出整个区间的众数）。

2. 基础知识准备

在深入之前，我们先明确几个关键概念：

众数定义：在一组数据中出现次数最多的值。如果多个值出现次数相同且都是最多，则这些值都是众数。

线段树特点：

• 每个节点代表一个区间
• 父节点信息可以从子节点信息合并得到
• 支持O(log n)的查询和更新

难点：众数没有直接的可合并性。例如：

• 左区间[1,2,2]的众数是2
• 右区间[3,3,4]的众数是3
• 但整体区间[1,2,2,3,3,4]的众数是2和3

3. 核心思想：摩尔投票法+线段树

我们采用摩尔投票法的变体思路。回忆经典摩尔投票法：

• 用于在O(n)时间、O(1)空间找到数组中出现次数超过一半的元素
• 基本思想：成对消除不同的元素，剩下的候选者可能是众数

在线段树中，我们为每个节点维护：

1. 候选众数（candidate）
2. 该候选在当前区间的"净计数"

关键观察：如果知道左右子区间的候选和计数，可以合并得到父区间的候选：

• 如果左右候选相同，则父候选为此值，计数为左右计数之和
• 如果左右候选不同，则父候选为计数较大的那个，计数为|左计数-右计数|

但这只能找到可能的候选，还需要验证它是否真的是整个区间的众数。

4. 数据结构设计

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        # 候选众数
        self.candidate = None
        # 候选的净计数（摩尔投票中的计数）
        self.count = 0
        # 用于验证的频率统计（需要额外处理）

5. 存储额外信息：频率映射

由于仅靠候选和计数无法确定真正的众数，我们需要额外存储信息来验证候选。这里有两种常见方案：

方案A：存储所有值的频率（适用于值域较小）

• 每个节点维护一个频率字典/数组
• 合并时合并频率表
• 查询时从频率表中找到最大值
• 缺点：空间开销大，合并操作慢

方案B：候选+频率查询（更优方案）

• 每个节点只存储候选和净计数
• 查询时，先得到候选
• 再用另一个数据结构（如另一棵线段树或BIT）快速查询候选在区间内的实际频率
• 时间复杂度：查询候选O(log n) + 验证O(log n)

这里我们采用方案B，但需要先解决如何快速查询任意值在区间内的频率。

6. 构建频率查询结构

为了查询任意值x在区间[L,R]中的出现次数，我们可以：

1. 为每个不同的值建立一个BIT/线段树
2. 在值的位置上标记1
3. 查询区间和即可得到频率

但这样空间开销太大。更好的方法是：

• 使用可持久化线段树（主席树）
• 但实现复杂

简化方案：我们暂时先实现一个较简单但不最优的版本，即每个节点存储频率映射（假设值域有限或已离散化）。

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        # 候选众数
        self.candidate = None
        # 候选的净计数
        self.count = 0
        # 频率映射（存储这个区间内主要候选的频率）
        # 实际上我们只存储有限个可能成为众数的值的频率
        self.freq = {}  # 或使用数组如果值域有限

7. 构建线段树

构建过程是递归的：

• 叶子节点：候选就是该元素本身，计数为1，频率映射中该元素频率为1
• 内部节点：合并左右子节点信息

合并算法：

def merge(left, right):
    node = SegmentTreeNode(left.start, right.end)
    
    # 第一步：确定候选
    if left.candidate == right.candidate:
        node.candidate = left.candidate
        node.count = left.count + right.count
    else:
        if left.count > right.count:
            node.candidate = left.candidate
            node.count = left.count - right.count
        else:
            node.candidate = right.candidate
            node.count = right.count - left.count
    
    # 第二步：合并频率映射
    # 只合并那些可能成为众数的元素的频率
    # 包括：左右候选、当前节点候选
    candidates_set = {left.candidate, right.candidate, node.candidate}
    node.freq = {}
    
    for cand in candidates_set:
        if cand is not None:
            # 计算cand在整个区间的频率
            freq = 0
            if cand in left.freq:
                freq += left.freq[cand]
            if cand in right.freq:
                freq += right.freq[cand]
            node.freq[cand] = freq
    
    return node

8. 查询操作

查询区间[L, R]的众数：

1. 递归查询得到该区间的线段树节点
2. 这个节点存储了候选和候选频率
3. 但我们需要验证候选是否真的是众数

查询步骤：

def query(node, L, R):
    if node.start >= L and node.end <= R:
        # 当前节点区间完全在查询区间内
        # 返回候选及其频率
        return node.candidate, node.freq.get(node.candidate, 0)
    
    if R <= (node.start + node.end) // 2:
        return query(node.left, L, R)
    elif L > (node.start + node.end) // 2:
        return query(node.right, L, R)
    
    # 查询跨越左右子树
    left_cand, left_freq = query(node.left, L, R)
    right_cand, right_freq = query(node.right, L, R)
    
    # 合并左右结果
    if left_cand == right_cand:
        candidate = left_cand
        count = left_freq + right_freq
    else:
        if left_freq > right_freq:
            candidate = left_cand
            count = left_freq
        else:
            candidate = right_cand
            count = right_freq
    
    return candidate, count

9. 更新操作

更新位置i的值为val：

1. 更新叶子节点
2. 向上更新所有祖先节点
3. 更新时需要重新计算频率映射

def update(node, i, val):
    if node.start == node.end:
        # 叶子节点
        old_val = node.candidate
        node.candidate = val
        node.count = 1
        node.freq = {val: 1}
        return old_val
    
    mid = (node.start + node.end) // 2
    old_val = None
    if i <= mid:
        old_val = update(node.left, i, val)
    else:
        old_val = update(node.right, i, val)
    
    # 重新合并子节点信息
    left = node.left
    right = node.right
    
    # 更新候选
    if left.candidate == right.candidate:
        node.candidate = left.candidate
        node.count = left.count + right.count
    else:
        if left.count > right.count:
            node.candidate = left.candidate
            node.count = left.count - right.count
        else:
            node.candidate = right.candidate
            node.count = right.count - left.count
    
    # 更新频率映射
    # 需要更新所有受影响的候选
    candidates_set = {left.candidate, right.candidate, node.candidate, old_val, val}
    node.freq = {}
    
    for cand in candidates_set:
        if cand is not None:
            freq = 0
            if cand in left.freq:
                freq += left.freq[cand]
            if cand in right.freq:
                freq += right.freq[cand]
            node.freq[cand] = freq
    
    return old_val

10. 时间复杂度分析

• 构建：O(n log n)，因为需要为每个节点构建频率映射
• 查询：O(log n)，但常数较大，因为需要合并结果
• 更新：O(log n)，需要更新从叶子到根路径上的所有节点
• 空间：O(n log n)在最坏情况下，因为每个节点存储频率映射

11. 优化方案

上述实现中频率映射的维护开销大。实际应用中常见优化：

方案1：值域分块

• 将值域分成√n块
• 对每块维护一个线段树
• 查询时检查每块的候选
• 时间复杂度：O(√n log n)

方案2：莫队算法

• 离线处理所有查询
• 通过调整区间边界来维护当前区间的频率
• 时间复杂度：O((n+q)√n)

方案3：可持久化线段树

• 为每个前缀建立线段树
• 查询时通过两棵线段树做差得到区间频率
• 时间复杂度：O(log n)，空间O(n log n)

12. 示例演示

假设数组为[1, 2, 2, 3, 2, 1, 1, 1]：

1. 构建线段树后，根节点：

   • 候选：1（通过摩尔投票法得到）
   • 频率：{1:4, 2:3, 3:1}

2. 查询[1,6]（索引从1开始）：

   • 实际区间值：[2,2,3,2,1,1]
   • 众数是2（出现3次）

3. 更新位置5为3：

   • 数组变为[1,2,2,3,3,1,1,1]
   • 重新计算频率

13. 实际应用注意事项

1. 多个众数：上述实现只返回一个众数。如果需要所有众数，需要修改为返回频率最大的所有元素。

2. 值域处理：如果值域很大，需要先离散化。

3. 内存优化：频率映射可以用更紧凑的结构存储，如只存储top-k候选。

4. 线程安全：如果需要并发访问，需要添加适当的同步机制。

14. 总结

线段树解决区间众数查询的关键在于：

1. 使用摩尔投票法的思想快速找到候选
2. 额外维护频率信息来验证候选
3. 通过合并操作支持高效的区间查询

虽然实现比标准的线段树应用复杂，但提供了O(log n)的查询和更新时间复杂度，适用于需要频繁查询和更新的场景。在实际应用中，可以根据具体需求选择不同的优化方案来平衡时间和空间复杂度。