Python 竞赛模板

输入输出

import sys
input = sys.stdin.readline        
sys.setrecursionlimit(10**6)   

n = int(input())
a, b = map(int, input().split())

arr = list(map(int, input().split()))

for _ in range(n):
    x = int(input())

# 读取到文件结尾
for line in sys.stdin:
    # 处理每一行
    list1 = map(int, line.strip().split())
    print(sum(list1))

# 格式化输出
print(" ".join(map(str, ans)))
print(*ans)                         # 空格分隔

# 交互题（必须加 flush）
print(f"? {mid}")
sys.stdout.flush()                  # 强制刷新缓冲区

常用数据结构

复杂度速查

操作	时间复杂度
列表 append/pop 末尾	O(1)
列表 insert/pop 开头	O(n)
列表 in 检查	O(n)
集合/字典 in 检查	O(1)
排序	O(n log n)
遍历所有元素	O(n)
堆 push/pop	O(log n)

列表操作

# 自动初始化为全0
a = [0] * n

# 二维列表
grid = [[0] * m for _ in range(n)]

# 列表推导式
squares = [x * x for x in range(n)]

# 列表推导式详解
# 基本格式: [表达式 for 变量 in 可迭代对象 if 条件]
# 等价于:
result = []
for x in iterable:
    if condition:
        result.append(expression)

# 示例: 读取 q 行整数
S_list = [int(input()) for _ in range(q)]

# 等价于:
S_list = []
for _ in range(q):
    S_list.append(int(input()))

# 条件表达式（三元运算符）
a = 'yes' if True else 'no'      # 'yes'
a = 'yes' if False else 'no'     # 'no'
path.extend(['RR' if flag else 'LL', 'D'])

# 反转
a.reverse()
a = a[::-1]

# 排序
a.sort()           # 原地排序
b = sorted(a)      # 返回新列表
# 降序排序
a.sort(reverse=True)      
b = sorted(a, reverse=True) 

# 最大/最小值
mx = max(a)
mn = min(a)
idx = a.index(max(a))

字符串

s = "hello"
lst = list(s)        # 字符串转列表
lst[0] = 'H'
s = ''.join(lst)     # 列表转字符串

s[::-1]              # 反转
s[::2]               # 隔一个取一个

s.isdigit()          # 全是数字
s.isalpha()          # 全是字母

''.join(dict.fromkeys(s))  # 字符串去重（保持顺序）

# join 用法
print(''.join(path))        # 列表元素直接拼接: ['R','R','D'] → 'RRD'
print(' '.join(path))       # 空格分隔: 'R R D'
print(','.join(map(str, lst)))  # 整数列表转字符串

# ord() 和 chr()（字符与ASCII码转换）
ord('A')      # 字符转 ASCII 码: 65
chr(97)       # ASCII 码转字符: 'a'

# 常用场景：字母序号转换
# A-Z: 65-90, a-z: 97-122, 0-9: 48-57
ord('A') - ord('A')  # 转成 0-25: 0
ord('B') - ord('A')  # 转成 0-25: 1

# 数字字符转数字
int('5')           # 5
ord('5') - ord('0') # 5 (字符'5'的ASCII码是53，'0'是48)

集合

s = set()
s.add(x)
s.remove(x)      # 不存在会报错
s.discard(x)     # 不存在不报错
s.pop()      # 删除并返回一个元素
print(x in s)           # 检查元素

# 集合运算
s1 & s2          # 交集
s1 | s2          # 并集
s1 - s2          # 差集
s1 ^ s2          # 对称差集

# set 没有 sort() 方法
# ✅ 正确：用 sorted()
lst = sorted(s)

字典

d = {}
d.get(key, default)    # 获取值，不存在返回 default

# 计数器：统计字符出现次数
from collections import Counter
cnt = Counter(arr)

# 增量赋值简化
d[key] = d.get(key, 0) + value

d = {'x': 1, 'y': 2}
for k, v in d.items():
    print(k, v)

defaultdict

from collections import defaultdict

# int 默认值：计数
d = defaultdict(int)
d["a"] += 1  # 不需要先判断键是否存在

# list 默认值：分组
d = defaultdict(list)
d["a"].append(1)  # 自动创建空列表

# 常用场景
# 1. 计数
s = "abracadabra"
cnt = defaultdict(int)
for char in s:
    cnt[char] += 1   # 不需要先判断键是否存在
# {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

# 对比普通字典：
d = {}
for char in s:
  if char not in d:
	  d[char] = 0
  d[char] += 1

# 2. 分组
words = ["apple", "banana", "apricot"]
group = defaultdict(list)
for w in words:
    group[w[0]].append(w)
# {'a': ['apple', 'apricot'], 'b': ['banana']}

堆（优先队列）

import heapq
heap = []              # 小顶堆（Python 只有小顶堆）
heapq.heapify(heap)   # 转堆
heapq.heappush(heap, x)  # 插入
heapq.heappop(heap)    # 弹出最小值
heap[0]               # 查看最小值
heapq.heapreplace(heap, x)  # 弹出+插入（原子操作）
# 大顶堆：存负值
heapq.heappush(heap, -x)
x = -heapq.heappop(heap)  # 取出时再取负，得到原值

房间分配（优先队列）

# 最少房间数：按到达时间排序，用小顶堆存储离开时间
def min_rooms(timetable):
    timetable.sort()  # 按到达时间排序
    heap = []
    for arrival, departure in timetable:
        if heap and arrival > heap[0]:  # 有房间空出
            heapq.heapreplace(heap, departure)
        else:  # 需要新房间
            heapq.heappush(heap, departure)
    return len(heap)

求 Top K 大元素：

def top_k(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    for x in arr[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

合并 K 个有序数组：

def merge_sorted_arrays(arrays):
    result = []
    heap = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]
    heapq.heapify(heap)
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(arrays[i]):
            heapq.heappush(heap, (arrays[i][j+1], i, j+1))
    return result

双端队列

from collections import deque

dq = deque()
dq.append(x)
dq.appendleft(x)
dq.pop()
dq.popleft()

单调队列

from collections import deque

# 求窗口最小值（递增队列）
q = deque()
for i in range(n):
    while q and q[0][0] < i - k:      # 超出窗口
        q.popleft()
    while q and q[-1][1] >= arr[i]:   # 队尾不优
        q.pop()
    q.append((i, arr[i]))
    min_val = q[0][1]

# 求窗口最大值（递减队列）
q = deque()
for i in range(n):
    while q and q[0][0] < i - k:
        q.popleft()
    while q and q[-1][1] <= arr[i]:
        q.pop()
    q.append((i, arr[i]))
    max_val = q[0][1]

常用算法

二分查找

在有序数组上查找

import bisect

arr = sorted([...])  # 先排序

# lower_bound: 第一个 >= x 的位置
pos = bisect.bisect_left(arr, x)

# upper_bound: 第一个 > x 的位置
pos = bisect.bisect_right(arr, x)

手动实现

# 查找左边界（第一个 >= target 的位置）
def lower_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 查找右边界（第一个 > target 的位置）
def upper_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

在单调函数上查找

def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """查找最大的 x 使得 f(x) = true"""
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整
        if f(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """查找最小的 x 使得 f(x) = true"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2  # 向下取整
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

滑动窗口

# 固定窗口大小 k
def sliding_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# 找到两个索引 i 和 j ，使得 a_i + a_j = x。
l = 0
r = n - 1
while l < r:
	sum = nums[l][0] + nums[r][0]
	if sum == x:
		print(nums[l][1] + 1, nums[r][1] + 1)
		exit()
	elif sum < x:
		l += 1
	else:
		r -= 1
print("IMPOSSIBLE")

可变窗口（双指针）

for r in range(n):
    sum_time += timeNeed[r]
    while sum_time > t and l <= r:
        sum_time -= timeNeed[l]
        l += 1
    ans = max(ans, r - l + 1)
    
for r in range(n):
    while arr[r] in s:
        s.remove(arr[l])
        l += 1
    s.add(arr[r])
    ans = max(ans, r - l + 1)
print(ans)

BFS/DFS

# 邻接表
adj = [[] for _ in range(n)]
adj[u].append(v)      # 有向边
adj[u].append((v, w))  # 带权重

# 无向图
adj[u].append(v)
adj[v].append(u)

DFS

def dfs(current_node):
	visited[current_node] = True
	for neighbor in adj[current_node]:
		if not visited[neighbor]:
			dfs(neighbor)

for i in range(n):
	if not visited[i]:
		dfs(i)

BFS

for i in range(n):
	if not visited[i]:
		q = deque([i])
		while q:
			node = q.popleft()
			visited[node] = True

			for neighbor in adj[node]:
				if not visited[neighbor]:
					q.append(neighbor)

前缀和

# 一维前缀和
prefix = [0] * (n + 1)
for i in range(n):
  prefix[i + 1] = prefix[i] + a[i]  # a 是 0-indexed

# 查询区间 [l, r]（1-indexed）
def query(l, r):
  return prefix[r] - prefix[l - 1]

# 二维前缀和
prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

全排列

from itertools import permutations, combinations

# 全排列
for perm in permutations(arr):
    print(list(perm))  # [1, 2, 3]

# 组合
for comb in combinations(arr, r):
    pass

差分数组

diff = [0] * (n + 1)

# 对区间 [l, r] 加 v
diff[l] += v
diff[r+1] -= v

# 还原
arr = [0] * n
curr = 0
for i in range(n):
    curr += diff[i]
    arr[i] = curr

动态规划

# ===== 1. 背包问题 =====
# 01 背包（每个物品选0或1次）
def knapsack_01(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # 倒序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 完全背包（每个物品可选无限次）
def knapsack_complete(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # 正序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 多重背包（每个物品可选有限次）- 二进制优化
def knapsack_multi(n, W, weights, values, counts):
    items = []  # 转化为01背包
    for i in range(n):
        k = 1
        c = counts[i]
        while c > 0:
            take = min(k, c)
            items.append((weights[i] * take, values[i] * take))
            c -= take
            k *= 2
    dp = [0] * (W + 1)
    for w, v in items:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

# ===== 计数DP（爬楼梯/骰子问题）=====
# 每次可以走1~k步，求到达n级台阶的走法数
def count_ways(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1  # 基础情况：到达0级只有1种方式（不走）
    for i in range(1, n + 1):
        dp[i] = sum(dp[max(0, i-k):i]) % MOD
    return dp[n]

# 简化为：每次走1~6步（骰子问题）
dp = [1]
for i in range(int(input())):
    dp.append(sum(dp[-6:]) % MOD)
print(dp[-1])

# ===== 2. 最长上升子序列 (LIS) =====
def lis(arr):
    import bisect
    dp = []
    for x in arr:
        pos = bisect.bisect_left(dp, x)
        if pos == len(dp):
            dp.append(x)
        else:
            dp[pos] = x
    return len(dp)

# ===== 3. 最长公共子序列 (LCS) =====
def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

# ===== 4. 编辑距离 =====
def edit_distance(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = i
    for j in range(m+1):
        dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

# ===== 5. 区间 DP =====
def interval_dp(n, cost):
    # dp[i][j] = 合并 i~j 的最小代价
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]

常用代码片段

# 2. 约瑟夫环
def josephus(n, k):
    if n == 1:
        return 0
    return (josephus(n-1, k) + k) % n

# 3. 回文判断
def is_palindrome(s):
    return s == s[::-1]

数论

质因数分解

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

K进制转换

# 数字 -> k进制字符串（每位对应字符集 s）
def idx_to_password(idx, k, m, s):
    res = []
    for _ in range(m):
        res.append(s[idx % k])
        idx //= k
    return ''.join(reversed(res))

# k进制字符串 -> 数字
def password_to_idx(password, k, s):
    idx = 0
    for ch in password:
        idx = idx * k + s.index(ch)
    return idx

四舍五入

# 1. 四舍五入（通用模板，避免浮点误差）
def round_div(a, b):
    # 计算 a / b，四舍五入到整数
    # 原理：判断小数部分是否 >= 0.5
    return a // b + (2 * (a % b) >= b)
# 示例：7 // 4 = 1，但 round_div(7, 4) = 2

约数

def get_divisors(n: int):
    """返回 1 到 n 所有数的约数列表"""
    divs = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            divs[j].append(i)
    return divs

# 最大公约数 / 最小公倍数
g = math.gcd(a, b)
lcm = a * b // g

# 约数枚举：求出 n 的所有约数（因数）
def divisors(n):
    small, large = [], []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
    return small + large[::-1]

素数

# 素数判断。直接调用 is_prime(n)
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

位运算

1 << i           # 2^i（左移，i=3 → 8）
# 判断
x & (1 << k)     # 检查第 k 位是否为 1
x >> k & 1       # 获取第 k 位的值

x.bit_length()   # 整数的二进制位数（5→3, 1→1, 0→0）
x.bit_count()    # 二进制中 1 的个数

x & -x           # 最低位 1（获取二进制最低位的 1）
x | 1            # 将最低位设为 1
x & ~1           # 将最低位设为 0
x ^ 1            # 翻转最低位

# 遍历检查某一位
for i in range(bit_count):
    if (S >> i) & 1:  # 检查第 i 位是否为 1
        # 第 i 位为 1
        pass

# 设置
x | (1 << k)     # 将第 k 位设为 1
x & ~(1 << k)    # 将第 k 位设为 0
x ^ (1 << k)     # 翻转第 k 位

# 常用
x & (x - 1)      # 清除最低位的 1
x | (x - 1)      # 将最低位 0 变成 1
x ^ (x + 1)      # 获取最低位不同的数

# 子集枚举
for sub in range(mask + 1):
    sub = (sub - 1) & mask  # 枚举子集（不包括 0）

# 最低位 1 的位置
bit = (x & -x).bit_length() - 1

常用

import math
import itertools
import bisect
from collections import deque, Counter, defaultdict

INF = 10**18          # 无穷大
MOD = 10**9 + 7       # 取模
PI = math.pi          # π
E = math.e            # e

# ❌ 列表 * n 可能是浅拷贝
a = [[0] * 3] * 3  # 错误！三个引用同一列表
a = [[0] * 3 for _ in range(3)]  # 正确

# 浮点数比较
abs(a - b) < 1e-9

提升（暂时不会）

图论模板

# ===== 二分图检测 =====
def is_bipartite(n, adj, node):
    """检测图是否为二分图，返回 (is_bipartite, min_changes)"""
    color = [-1] * n  # -1: 未染色, 0/1: 颜色
    ans = 0

    for i in range(n):
        if color[i] != -1:
            continue
        q = deque([i])
        color[i] = 0
        res = [0, 0]

        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False, 0
            res[0] += color[u] ^ node[u]
            res[1] += (color[u] ^ 1) ^ node[u]

        ans += min(res)

    return True, ans

# 使用示例
# node[i] 为初始颜色(0或1)，adj 为邻接表
# ok, changes = is_bipartite(n, adj, node)
# if not ok: print("Impossible")

# 使用：node[i] 为 0 或 1 表示初始颜色
# 返回 (is_bipartite, min_changes)

# ===== 拓扑排序 =====
def topological_sort():
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]:
            in_degree[v] += 1
    q = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    while q:
        u = q.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    return result if len(result) == n else []  # 有环返回空

# ===== Dijkstra（单源最短路）=====
def dijkstra(start):
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]  # (距离, 节点)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# ===== Kruskal（最小生成树）=====
def kruskal(edges, n):
    edges.sort()
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    return sum(w for w, u, v in edges if union(u, v))

并查集 (DSU)

1. 基础用法（函数式）

n = 5
parent = list(range(n))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        parent[px] = py

union(0, 1)
union(1, 2)
print(find(0) == find(2))  # True

2. 朋友圈/连通分量

def count_components(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py

    for u, v in edges:
        union(u, v)

    return len(set(find(i) for i in range(n)))

3. Kruskal 最小生成树

Kruskal 算法已合并到上一节”图论模板”中。

4. 类实现（推荐）

class DSU:
    """并查集 (Disjoint Set Union) - 带路径压缩 + 按秩合并"""

    def __init__(self, n: int = 0):
        self.init(n)

    def init(self, n: int):
        self.n = n
        self.cnt = n
        self.f = list(range(n))
        self.siz = [1] * n

    def find(self, x: int) -> int:
        while x != self.f[x]:
            self.f[x] = self.f[self.f[x]]
        return self.f[x]

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def merge(self, x: int, y: int) -> bool:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.siz[x] < self.siz[y]:
            x, y = y, x
        self.f[y] = x
        self.siz[x] += self.siz[y]
        self.cnt -= 1
        return True

    def size(self, x: int) -> int:
        return self.siz[self.find(x)]

    def count(self) -> int:
        return self.cnt

# 竞赛输入输出模板
size, query_num = [int(i) for i in input().split()]
dsu = DSU(size)
for _ in range(query_num):
    q_type, u, v = [int(i) for i in input().split()]
    if q_type == 0:
        dsu.merge(u, v)
    else:
        print(1 if dsu.same(u, v) else 0)

树状数组 (Fenwick Tree)

class Fenwick:
    """树状数组 (Fenwick Tree / Binary Indexed Tree)"""

    def __init__(self, n: int = 0):
        self.n = n
        self.a = [0] * n

    def init(self, n: int):
        self.n = n
        self.a = [0] * n

    def add(self, x: int, v):
        """在位置 x 加上 v (0-indexed)"""
        i = x + 1
        while i <= self.n:
            self.a[i - 1] = self.a[i - 1] + v
            i += i & -i

    def sum(self, x: int):
        """求前缀和 [0, x] (0-indexed, 包含 x)"""
        ans = 0
        i = x + 1
        while i > 0:
            ans = ans + self.a[i - 1]
            i -= i & -i
        return ans

    def range_sum(self, l: int, r: int):
        """求区间和 [l, r] (0-indexed, 包含两端)"""
        if l == 0:
            return self.sum(r)
        return self.sum(r) - self.sum(l - 1)

    def select(self, k):
        """找到满足 sum(i) <= k 的最大 i"""
        x = 0
        cur = 0
        i = 1 << (self.n.bit_length() - 1)
        while i:
            if x + i <= self.n and cur + self.a[x + i - 1] <= k:
                x += i
                cur = cur + self.a[x - 1]
            i >>= 1
        return x

区间最值查询 (RMQ)

class RMQ:
    """区间最值查询 (Range Minimum Query)"""

    def __init__(self, v=None):
        if v is not None:
            self.init(v)

    def init(self, v):
        """初始化数组 v"""
        import math
        n = len(v)
        self.n = n
        self.B = 64

        self.pre = v[:]
        self.suf = v[:]
        self.ini = v[:]

        if n == 0:
            return

        M = (n - 1) // self.B + 1
        lg = math.log2(M)

        self.a = [[None] * M for _ in range(int(lg) + 1)]

        # 预处理每个块内的最小值
        for i in range(M):
            self.a[0][i] = v[i * self.B]
            for j in range(1, self.B):
                if i * self.B + j < n:
                    self.a[0][i] = min(self.a[0][i], v[i * self.B + j])

        # 前缀最小值
        for i in range(1, n):
            if i % self.B:
                self.pre[i] = min(self.pre[i], self.pre[i - 1])

        # 后缀最小值
        for i in range(n - 2, -1, -1):
            if i % self.B != self.B - 1:
                self.suf[i] = min(self.suf[i], self.suf[i + 1])

        # Sparse Table
        j = 1
        while (1 << j) <= M:
            for i in range(M - (1 << j) + 1):
                self.a[j][i] = min(self.a[j - 1][i], self.a[j - 1][i + (1 << (j - 1))])
            j += 1

    def query(self, l: int, r: int):
        """查询区间 [l, r] 的最小值"""
        import math
        if l > r:
            return float('inf')
        if l // self.B != (r - 1) // self.B:
            ans = min(self.suf[l], self.pre[r - 1])
            l = l // self.B + 1
            r = r // self.B
            if l < r:
                k = int(math.log2(r - l))
                ans = min(ans, self.a[k][l], self.a[k][r - (1 << k)])
            return ans
        else:
            x = self.B * (l // self.B)
            # 简化的同块查询
            return min(self.ini[l:r + 1])

埃拉托斯特尼筛法

minp = []
primes = []

def sieve(n: int):
    """埃拉托斯特尼筛法 - 计算 minp 和 primes"""
    global minp, primes
    minp = [0] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if minp[i] == 0:
            minp[i] = i
            primes.append(i)

        for p in primes:
            if i * p > n:
                break
            minp[i * p] = p
            if p == minp[i]:
                break

矩阵快速幂

def mat_mul(A, B):
    n = len(A)
    m = len(B[0])
    k = len(B)
    return [[sum(A[i][p] * B[p][j] for p in range(k)) % MOD for j in range(m)] for i in range(n)]

def mat_pow(A, n):
    # 单位矩阵
    result = [[int(i==j) for j in range(len(A))] for i in range(len(A))]
    while n:
        if n & 1:
            result = mat_mul(result, A)
        A = mat_mul(A, A)
        n >>= 1
    return result

# 使用示例：计算斐波那契数列第 n 项
# 矩阵 [[1,1], [1,0]] 的 n 次方
fib_matrix = [[1,1], [1,0]]
result = mat_pow(fib_matrix, 10)
print(result[0][1])  # 第 10 项斐波那契数

树状数组（Fenwick Tree）

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l-1)

# 使用示例：动态前缀和
bit = BIT(5)
bit.add(1, 5)  # 第1位加5
bit.add(3, 10)  # 第3位加10
print(bit.sum(3))  # 前3位的和 = 15
print(bit.range_sum(2, 4))  # 2到4位的和 = 10

二维网格操作

# 4方向移动
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dx, dy in dirs:
    nx, ny = x + dx, y + dy

# 8方向移动
dirs8 = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

# 判断边界
if 0 <= nx < n and 0 <= ny < m:
    # 有效

数论（扩展部分）

# 埃拉托斯特尼筛法: 快速筛选出 1~n 范围内的所有质数
# 使用：primes = sieve(n) 返回质数列表
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

# 快速幂：计算 a^b mod mod，高效处理大数幂运算
# 使用：pow_mod(2, 10, 1000) = 24 (2^10=1024 mod 1000)
def pow_mod(a, b, mod):
    res = 1
    a %= mod
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

# 组合数（预计算）：计算组合数 C(n, k) = n! / (k!(n-k)!)
# - 使用：fact, inv_fact = comb_init(1000000, MOD)
# 		 print(C(100, 50, MOD, fact, inv_fact))
# - 注意：需要 MOD 为质数（常用 10^9+7）
def comb_init(n, mod):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % mod
    return fact, inv_fact

def C(n, k, mod, fact, inv_fact):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

# 乘法逆元：求 a 在模 mod 下的逆元（即 a^(-1) mod mod）
# 使用：modinv(3, 7) = 5（因为 3*5=15≡1 mod 7）
def modinv(a, mod):
    return pow(a, mod-2, mod)
    
# 扩展欧几里得（求逆元）
def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, g = exgcd(b, a % b)
    return y, x - (a // b) * y, g