- 正确答案：对区间做 max/min 的增删改查（即支持区间最值查询、单点修改、区间修改、甚至动态插入/删除端点），需根据具体操作类型选择合适的数据结构。常见高效方案包括：线段树（带懒标记）、稀疏表（ST 表，仅静态）、单调队列（滑动窗口场景）、平衡二叉搜索树（如 C++ set 或 Java TreeSet 配合离散化）、以及更高级的结构如分块（sqrt decomposition）或笛卡尔树（Cartesian Tree）配合 LCA 求 RMQ。若支持动态插入/删除区间端点（如维护一组不重叠区间，并频繁合并、分裂、查覆盖区间的 max/min），则需结合区间树（Interval Tree）或线段树动态开点 + 离散化 + 标记永久化。 - 解答思路：第一步，明确操作类型——是静态数组上的 RMQ（Range Maximum/Minimum Query）？还是带单点更新的动态 RMQ？是否支持区间赋值/加法更新？是否需要支持动态增删区间（如维护活跃时间段集合）？不同需求对应不同工具。第二步，分析时间/空间约束——校园招聘题通常要求 O(log n) 查询与更新，故线段树是最通用、可扩展性最强的选择；若只查询不修改，ST 表 O(1) 查询 + O(n log n) 预处理最优；若为滑动窗口固定长度，则单调队列 O(n) 总时间、O(1) 均摊查询。第三步，考虑底层实现细节——max/min 线段树本质是维护每个节点对应区间的最值，合并时取左右子节点最值；懒标记需支持“覆盖”（set）或“增量”（add）语义；动态增删端点时，需将坐标离散化，并用动态开点线段树或平衡树维护有效位置集合。 - 深度知识讲解：（1）线段树维护区间最值的底层原理：每个节点 node[l,r] 存储 seg[node] = max{a[i] | i ∈ [l,r]}。建树过程自底向上合并：seg[node] = max(seg[left], seg[right])。单点修改时从叶子向上更新路径上所有祖先节点，时间复杂度 O(log n)。区间查询时将查询区间 [ql,qr] 分解为 O(log n) 个不相交的线段树节点区间，取其最大值。（2）懒标记设计：若支持区间赋值（如 assign [l,r] = v），则 lazy[node] 表示该节点对应整个区间被统一设为某值（需标记 is_set）；若支持区间加法（如 add [l,r] += v），则 lazy[node] 为待下传的增量，push_down 时左右子节点最值和懒标记均需加上该增量。注意：max/min 不满足线性叠加性，因此“区间加法”更新后无法直接由旧最值得到新最值——必须下传并递归更新叶子，或采用“懒标记+标记下传+合并时重新计算”策略。实际上，纯 max/min 线段树支持区间加法更新是低效的（因加法会改变相对大小关系，无法避免遍历叶子），故工业级实现中，若需区间加法 + 区间最值，常改用分块（每块维护最值+块内加法懒标记）或线段树套平衡树（不现实），更实际的是接受 O(n) 最坏更新——因此面试中应主动澄清：题目中的“区间修改”是指覆盖（set）还是增量（add）？这直接影响方案选择。（3）动态增删区间端点（如维护一个区间集合 S = {[l_i, r_i]}，支持 insert([l,r]), delete([l,r]), query_max_covered_point() 即求被最多区间覆盖的位置上的最大左端点？或 query_max_intersection_length？）。此时核心是“事件扫描线 + 平衡树”：将所有端点作为事件（l → +1, r+1 → -1），用 map 维护当前坐标处的覆盖变化量，再用 multiset 动态维护当前所有活跃左端点；扫描过程中，用堆或 multiset 维护当前覆盖数最大的位置对应的候选值。另一种正统做法是使用区间树（Augmented BST）：每个节点存储子树对应区间的 max_r 和 min_l，并支持 O(log n) 查找与给定区间重叠的所有区间。但校园招聘中更可能考察的是“离线+离散化+差分+线段树”组合：例如，所有插入/删除操作预先读入，提取所有端点离散化为 1..m，然后用线段树维护每个离散点的覆盖次数，再在每个叶节点存该点原始坐标及对应值（如 max_left），查询时在线段树上查找覆盖次数最大的叶子中，对应原始坐标的 max/min 属性。（4）ST 表的底层：基于倍增思想，st[i][j] 表示从位置 i 开始、长度为 2^j 的区间的最值。预处理：st[i][0] = a[i]；st[i][j] = max(st[i][j-1], st[i + 2^(j-1)][j-1])。查询 [l,r] 时，令 len = r-l+1，k = floor(log2(len))，则答案为 max(st[l][k], st[r - 2^k + 1][k])。本质是用两个有重叠的 2^k 区间覆盖 [l,r]，利用幂等性（max(x,x)=x）保证正确性。但不支持修改。（5）单调队列用于滑动窗口最值：维护双端队列 dq，存索引，保持队列内 a[dq[i]] 严格递减（对 max）或递增（对 min），且 dq.front() 始终是当前窗口最值索引。入队时从队尾弹出所有 ≤ 当前值（max 场景）的元素；出窗时检查 dq.front() 是否 < 当前左边界。每个元素至多入队出队一次，O(n) 时间。 - 伪代码（动态区间 max 查询 + 单点修改的线段树）： ``` const int N = 1e5 + 10; int tree[4*N], a[N]; void build(int node, int l, int r) { if (l == r) { tree[node] = a[l]; return; } int mid = (l + r) / 2; build(node*2, l, mid); build(node*2+1, mid+1, r); tree[node] = max(tree[node*2], tree[node*2+1]); } void update(int node, int l, int r, int idx, int val) { if (l == r) { tree[node] = val; return; } int mid = (l + r) / 2; if (idx <= mid) update(node*2, l, mid, idx, val); else update(node*2+1, mid+1, r, idx, val); tree[node] = max(tree[node*2], tree[node*2+1]); } int query(int node, int l, int r, int ql, int qr) { if (qr < l || r < ql) return INT_MIN; if (ql <= l && r <= qr) return tree[node]; int mid = (l + r) / 2; return max(query(node*2, l, mid, ql, qr), query(node*2+1, mid+1, r, ql, qr)); } ``` - 扩展知识：若面试题隐含“在线、高并发、内存受限”，可提 Redis 的 Sorted Set（zset）用 score 做区间端点、value 存元数据，配合 ZRANGEBYSCORE 实现范围 max/min ——但这属于工程权衡，非算法本质。另外，“区间最值”与“LIS/LDS”“最长上升子序列”存在联系：例如，用线段树优化 DP 状态转移 f[i] = max{f[j]} + 1（j < i and a[j] < a[i]），此时线段树按 a[j] 离散化为下标，维护值域上的最大 f[j]，实现 O(n log n)。这也体现了 max 线段树作为 DP 加速器的核心价值。最后强调：面试中务必先反问确认操作集（query only? point update? range update? insert/delete interval?），再给出匹配方案——这比强行套模板更能体现工程素养。

京东推荐算法 27日常实习二面

全站热榜

创作者周榜