1. 位运算与贪心算法的组合应用位运算在算法竞赛和实际工程中都有着广泛的应用场景。当它与贪心算法结合时往往能解决一些看似复杂的问题。让我们从一个经典案例开始给定一个非负整数数组如何找到两个数的异或结果最大值1.1 位运算基础回顾位运算包括与()、或(|)、异或(^)、取反(~)、左移()和右移()六种基本操作。在解决实际问题时我们常常需要使用掩码技术提取特定位通过位移操作快速计算2的幂次方利用异或性质实现数值交换或查找唯一数例如判断一个数是否是2的幂次方可以用def is_power_of_two(n): return n 0 and (n (n - 1)) 01.2 贪心策略在位运算中的应用贪心算法在每一步选择当前最优解最终希望达到全局最优。当与位运算结合时常见的策略有从最高位开始逐位确定最优解在每一步选择使当前位最优的选项通过位掩码记录已做出的选择以最大异或对问题为例我们可以构建一个Trie树然后对每个数字从高位到低位贪心地选择与当前位相反的路径如果存在。1.3 实际案例子集最大异或和给定一个数组找出其所有子集的异或和的最大值。这个问题可以通过贪心地从最高位开始尝试构造每一位为1的解def max_xor_subset(nums): max_xor 0 mask 0 for i in range(30, -1, -1): mask | 1 i prefixes {num mask for num in nums} temp max_xor | (1 i) for p in prefixes: if (p ^ temp) in prefixes: max_xor temp break return max_xor这个算法的时间复杂度是O(n log MAX_VAL)其中MAX_VAL是数组中元素的最大值。2. 构造型问题中的贪心策略构造型问题要求我们按照特定规则构建一个满足条件的解。贪心算法在这种问题中往往能提供简洁高效的解决方案。2.1 区间调度问题经典的区间调度问题要求选择最多的不重叠区间。贪心策略是按照结束时间排序然后每次选择结束最早的且不与已选区间重叠的区间def interval_scheduling(intervals): intervals.sort(keylambda x: x[1]) selected [] last_end -float(inf) for start, end in intervals: if start last_end: selected.append((start, end)) last_end end return selected2.2 任务分配问题考虑有n个任务和m个工人如何分配任务使最大工作时间最小化。贪心策略是将最耗时的任务分配给当前工作量最小的工人import heapq def task_assignment(tasks, m): workers [0] * m heapq.heapify(workers) tasks.sort(reverseTrue) for task in tasks: min_worker heapq.heappop(workers) heapq.heappush(workers, min_worker task) return max(workers)这个实现使用了最小堆来高效地找到当前工作量最小的工人时间复杂度为O(n log m)。2.3 构造特定序列有时需要构造满足特定性质的序列。例如构造一个排列使得相邻元素的异或和最大。对于n是2的幂次方的情况可以构造格雷码序列def gray_code(n): return [i ^ (i 1) for i in range(1 n)]格雷码的特点是相邻两个数只有一位不同因此它们的异或结果是一个2的幂次方。3. 扫描线与前缀和的高级应用扫描线算法是处理几何问题和区间问题的有力工具结合前缀和可以高效解决许多复杂问题。3.1 二维区间覆盖问题考虑一个二维平面上有多个矩形如何计算被至少k个矩形覆盖的区域面积扫描线算法步骤如下将所有矩形的左右边界作为事件点沿x轴扫描维护当前x区间内y轴上的覆盖次数使用线段树或差分数组维护y轴上的覆盖情况def rectangle_area(rectangles, k): events [] for x1, y1, x2, y2 in rectangles: events.append((x1, start, y1, y2)) events.append((x2, end, y1, y2)) events.sort() active_intervals [] prev_x None total_area 0 for x, typ, y1, y2 in events: if prev_x is not None and x ! prev_x: delta_x x - prev_x # 计算当前y轴上被至少k次覆盖的总长度 covered_length compute_k_coverage(active_intervals, k) total_area delta_x * covered_length if typ start: active_intervals.append((y1, y2)) active_intervals.sort() else: active_intervals.remove((y1, y2)) prev_x x return total_area3.2 高维前缀和SOS DP高维前缀和可以高效计算子集的和。例如给定数组a对于所有mask计算所有i⊆mask的a[i]之和def sos_dp(a, n): dp a.copy() for i in range(n): for mask in range(1 n): if mask (1 i): dp[mask] dp[mask ^ (1 i)] return dp这个算法的时间复杂度是O(n 2^n)适用于n较小的情况通常n≤20。3.3 实际应用图像处理中的位运算在图像处理中位运算常用于图像合成通过位运算组合多个图像的掩码特征提取使用位掩码提取特定颜色通道快速计算利用位运算优化像素值计算例如将两张图像按位与操作import cv2 import numpy as np img1 cv2.imread(image1.png) img2 cv2.imread(image2.png) result cv2.bitwise_and(img1, img2) cv2.imwrite(result.png, result)4. 并查集与枚举的组合技巧并查集是一种高效处理不相交集合的数据结构结合枚举技巧可以解决许多复杂问题。4.1 带权并查集带权并查集可以维护节点间的相对关系。例如在食物链问题中我们需要维护三种动物之间的捕食关系class WeightedUnionFind: def __init__(self, size): self.parent list(range(size)) self.weight [0] * size def find(self, x): if self.parent[x] ! x: orig_parent self.parent[x] self.parent[x] self.find(self.parent[x]) self.weight[x] self.weight[orig_parent] return self.parent[x] def union(self, x, y, w): root_x self.find(x) root_y self.find(y) if root_x ! root_y: self.parent[root_x] root_y self.weight[root_x] self.weight[y] w - self.weight[x]4.2 枚举并查集解决约束满足问题考虑一个问题有n个变量和m个约束条件每个约束形如x_i - x_j ≤ c_k。我们可以枚举变量的可能取值使用并查集检查约束是否满足通过路径压缩优化查询效率4.3 实际案例离线查询处理在处理大量离线查询时可以按照特定顺序处理查询使用并查集维护当前状态def process_queries(queries, n): queries.sort(keylambda q: q.priority) # 按特定优先级排序 uf UnionFind(n) results [] for query in queries: if query.type union: uf.union(query.u, query.v) else: results.append(uf.find(query.u) uf.find(query.v)) return results这种模式常用于处理动态连通性问题其中查询可以离线处理。5. 前后缀分解技术前后缀分解是一种将问题分解为前缀和后缀两部分分别处理的技巧常用于优化时间复杂度。5.1 最大子数组和问题经典的最大子数组和问题可以用前后缀思想解决def max_subarray(nums): max_prefix max_suffix max_sub current nums[0] for num in nums[1:]: current max(num, current num) max_sub max(max_sub, current) # 计算前缀最大值和后缀最大值 prefix [0] * len(nums) prefix[0] nums[0] for i in range(1, len(nums)): prefix[i] prefix[i-1] nums[i] suffix [0] * len(nums) suffix[-1] nums[-1] for i in range(len(nums)-2, -1, -1): suffix[i] suffix[i1] nums[i] return max_sub, prefix, suffix5.2 乘积最大子数组类似地乘积最大子数组需要考虑正负号的影响def max_product(nums): max_pre min_pre max_sub nums[0] for num in nums[1:]: candidates (num, max_pre * num, min_pre * num) max_pre max(candidates) min_pre min(candidates) max_sub max(max_sub, max_pre) return max_sub5.3 前后缀在字符串处理中的应用在字符串问题中前后缀数组常用于快速查询def build_prefix_suffix(s, pattern): # 构建KMP算法中的部分匹配表 lps [0] * len(pattern) length 0 for i in range(1, len(pattern)): while length 0 and pattern[i] ! pattern[length]: length lps[length - 1] if pattern[i] pattern[length]: length 1 lps[i] length return lps6. 区间去重查询技术区间去重查询要求统计区间内不同元素的数量有多种高效解决方案。6.1 离线处理莫队算法莫队算法通过对查询进行分块排序来优化时间复杂度def mo_algorithm(queries, n, array): block_size int(n**0.5) queries sorted(enumerate(queries), keylambda x: (x[1][0]//block_size, x[1][1])) current_l current_r 0 current_count 0 count [0] * (max(array) 1) results [0] * len(queries) for query in queries: idx, (l, r) query while current_l l: current_l - 1 if count[array[current_l]] 0: current_count 1 count[array[current_l]] 1 while current_r r: if count[array[current_r]] 0: current_count 1 count[array[current_r]] 1 current_r 1 while current_l l: count[array[current_l]] - 1 if count[array[current_l]] 0: current_count - 1 current_l 1 while current_r r: current_r - 1 count[array[current_r]] - 1 if count[array[current_r]] 0: current_count - 1 results[idx] current_count return results6.2 在线处理持久化线段树对于需要在线处理的情况可以使用持久化线段树class PersistentSegmentTree: def __init__(self, size): self.size size self.versions [] self.nodes [] def update(self, version, pos, value): new_root len(self.nodes) self.nodes.append(None) def _update(node, l, r): if l r: self.nodes.append({sum: value}) return len(self.nodes) - 1 mid (l r) // 2 new_node {left: self.nodes[node][left], right: self.nodes[node][right]} if pos mid: new_node[left] _update(new_node[left], l, mid) else: new_node[right] _update(new_node[right], mid1, r) new_node[sum] self.nodes[new_node[left]][sum] self.nodes[new_node[right]][sum] self.nodes.append(new_node) return len(self.nodes) - 1 new_version _update(self.versions[version], 0, self.size - 1) self.versions.append(new_version) return len(self.versions) - 1 def query(self, version, l, r): def _query(node, node_l, node_r): if r node_l or l node_r: return 0 if l node_l and node_r r: return self.nodes[node][sum] mid (node_l node_r) // 2 return _query(self.nodes[node][left], node_l, mid) _query(self.nodes[node][right], mid1, node_r) return _query(self.versions[version], 0, self.size - 1)7. 线段树的高级设计模式线段树是一种灵活的数据结构可以通过不同的设计解决各类区间查询问题。7.1 动态开点线段树当区间范围很大但实际使用点稀疏时可以使用动态开点技术class DynamicSegmentTreeNode: __slots__ [left, right, sum] def __init__(self): self.left None self.right None self.sum 0 class DynamicSegmentTree: def __init__(self, min_val, max_val): self.root DynamicSegmentTreeNode() self.min_val min_val self.max_val max_val def update(self, index, value): def _update(node, l, r): if l r: node.sum value return mid (l r) // 2 if index mid: if not node.left: node.left DynamicSegmentTreeNode() _update(node.left, l, mid) else: if not node.right: node.right DynamicSegmentTreeNode() _update(node.right, mid1, r) node.sum (node.left.sum if node.left else 0) (node.right.sum if node.right else 0) _update(self.root, self.min_val, self.max_val) def query(self, ql, qr): def _query(node, l, r): if not node or r ql or l qr: return 0 if ql l and r qr: return node.sum mid (l r) // 2 return _query(node.left, l, mid) _query(node.right, mid1, r) return _query(self.root, self.min_val, self.max_val)7.2 线段树维护复杂信息线段树可以维护各种复杂信息如区间GCD、区间最大子段和等class SegmentTreeNode: def __init__(self): self.sum 0 self.max_prefix 0 self.max_suffix 0 self.max_subarray 0 self.left None self.right None class AdvancedSegmentTree: def __init__(self, data): self.n len(data) self.root self._build(0, self.n - 1, data) def _build(self, l, r, data): node SegmentTreeNode() if l r: val data[l] node.sum val node.max_prefix max(0, val) node.max_suffix max(0, val) node.max_subarray max(0, val) return node mid (l r) // 2 node.left self._build(l, mid, data) node.right self._build(mid 1, r, data) node.sum node.left.sum node.right.sum node.max_prefix max(node.left.max_prefix, node.left.sum node.right.max_prefix) node.max_suffix max(node.right.max_suffix, node.right.sum node.left.max_suffix) node.max_subarray max(node.left.max_subarray, node.right.max_subarray, node.left.max_suffix node.right.max_prefix) return node def query_max_subarray(self, ql, qr): def _query(node, l, r): if r ql or l qr: return (0, 0, 0, 0) if ql l and r qr: return (node.sum, node.max_prefix, node.max_suffix, node.max_subarray) mid (l r) // 2 left_sum, left_pre, left_suf, left_sub _query(node.left, l, mid) right_sum, right_pre, right_suf, right_sub _query(node.right, mid 1, r) total_sum left_sum right_sum max_prefix max(left_pre, left_sum right_pre) max_suffix max(right_suf, right_sum left_suf) max_sub max(left_sub, right_sub, left_suf right_pre) return (total_sum, max_prefix, max_suffix, max_sub) _, _, _, result _query(self.root, 0, self.n - 1) return result7.3 线段树的区间修改操作线段树支持多种区间修改操作如区间加、区间乘、区间赋值等class LazySegmentTree: def __init__(self, data): self.n len(data) self.size 1 while self.size self.n: self.size 1 self.tree [0] * (2 * self.size) self.lazy_add [0] * (2 * self.size) self.lazy_mul [1] * (2 * self.size) for i in range(self.n): self.tree[self.size i] data[i] for i in range(self.size - 1, 0, -1): self.tree[i] self.tree[2 * i] self.tree[2 * i 1] def push(self, node, node_l, node_r): if self.lazy_mul[node] ! 1 or self.lazy_add[node] ! 0: mid (node_l node_r) // 2 left_len mid - node_l 1 right_len node_r - mid # 更新左子树 self.tree[2 * node] self.tree[2 * node] * self.lazy_mul[node] self.lazy_add[node] * left_len self.lazy_mul[2 * node] * self.lazy_mul[node] self.lazy_add[2 * node] self.lazy_add[2 * node] * self.lazy_mul[node] self.lazy_add[node] # 更新右子树 self.tree[2 * node 1] self.tree[2 * node 1] * self.lazy_mul[node] self.lazy_add[node] * right_len self.lazy_mul[2 * node 1] * self.lazy_mul[node] self.lazy_add[2 * node 1] self.lazy_add[2 * node 1] * self.lazy_mul[node] self.lazy_add[node] # 重置当前节点的懒标记 self.lazy_mul[node] 1 self.lazy_add[node] 0 def range_mul_add(self, l, r, mul, add): def _update(node, node_l, node_r): if r node_l or l node_r: return if l node_l and node_r r: self.tree[node] self.tree[node] * mul add * (node_r - node_l 1) self.lazy_mul[node] * mul self.lazy_add[node] self.lazy_add[node] * mul add return self.push(node, node_l, node_r) mid (node_l node_r) // 2 _update(2 * node, node_l, mid) _update(2 * node 1, mid 1, node_r) self.tree[node] self.tree[2 * node] self.tree[2 * node 1] _update(1, 0, self.size - 1) def query_range(self, l, r): def _query(node, node_l, node_r): if r node_l or l node_r: return 0 if l node_l and node_r r: return self.tree[node] self.push(node, node_l, node_r) mid (node_l node_r) // 2 return _query(2 * node, node_l, mid) _query(2 * node 1, mid 1, node_r) return _query(1, 0, self.size - 1)在实际工程中线段树的实现可以根据具体问题进行优化。例如对于二维问题可以使用二维线段树或线段树套平衡树对于高维问题可以使用KD树等变种。线段树的强大之处在于它的灵活性几乎可以维护任何满足区间可加性的信息。