Algorithm Roadmap
点击节点查看题目列表，参考 灵茶山艾府 - 如何科学刷题？。
100%
Topic Title
Progress 0 / 0 (0%)
Prerequisites
Problems
滑动窗口与双指针
一、定长滑动窗口
§1.1 基础
【套路】教你解决定长滑窗！适用于所有定长滑窗题目！
ID
Problem
Score
§1.2 进阶（选做）
ID
Problem
Score
§1.3 其他（选做）
ID
Problem
Score
二、不定长滑动窗口
不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。
注：滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。
§2.1 越短越合法/求最长/最大
§2.1.1 基础
ID
Problem
Score
§2.1.2 进阶（选做）
ID
Problem
Score
§2.2 越长越合法/求最短/最小
ID
Problem
Score
§2.3 求子数组个数
§2.3.1 越短越合法
一般要写 ans += right - left + 1。
内层循环结束后，[left,right] 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 [left,right]，还有 [left+1,right],[left+2,right],…,[right,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 left,left+1,left+2,…,right 的所有子数组都是满足要求的，这一共有 right−left+1 个。
ID
Problem
Score
§2.3.2 越长越合法
一般要写 ans += left。
内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个。
我们关注的是 left−1 的合法性，而不是 left。
ID
Problem
Score
§2.3.3 恰好型滑动窗口
例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：
计算有多少个元素和 ≥k 的子数组。
计算有多少个元素和 >k，也就是 ≥k+1 的子数组。
答案就是元素和 ≥k 的子数组个数，减去元素和 ≥k+1 的子数组个数。这里把 > 转换成 ≥，从而可以把滑窗逻辑封装成一个函数 solve，然后用 solve(k)−solve(k+1) 计算，无需编写两份滑窗代码。
总结：「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。
注：也可以把问题变成 ≤k 减去 ≤k−1，即两个「至多」。可根据题目选择合适的变形方式。
注：也可以把两个滑动窗口合并起来，维护同一个右端点 right 和两个左端点 left1 和 left2 ，我把这种写法叫做三指针滑动窗口。
ID
Problem
Score
§2.4 其他（选做）
ID
Problem
Score
二分算法
一、二分查找
讲解：二分查找 红蓝染色法【基础算法精讲 04】
设 nums 为递增（非递减）数组，长为 n。
需求 写法 如果不存在
≥x 的第一个元素的下标 lowerBound(nums,x) 结果为 n
>x 的第一个元素的下标 lowerBound(nums,x+1) 结果为 n
<x 的最后一个元素的下标 lowerBound(nums,x)−1 结果为 −1
≤x 的最后一个元素的下标 lowerBound(nums,x+1)−1 结果为 −1
需求 写法
<x 的元素个数 lowerBound(nums,x)
≤x 的元素个数 lowerBound(nums,x+1)
≥x 的元素个数 n−lowerBound(nums,x)
>x 的元素个数 n−lowerBound(nums,x+1)
注意 <x 和 ≥x 互为补集，二者之和为 n。≤x 和 >x 同理。
§1.1 基础
ID
Problem
Score
§1.2 进阶
部分题目需要先排序，然后在有序数组上二分查找。
ID
Problem
Score
二、二分答案
“花费一个 log 的时间，增加了一个条件。” —— 二分答案
§2.1 求最小
题目求什么，就二分什么。
答疑
问：如何把二分答案与数组上的二分查找联系起来？
答：假设答案在区间 [2,5] 中，我们相当于在一个虚拟数组 [check(2),check(3),check(4),check(5)] 中二分找第一个（或者最后一个）值为 true 的 check(x)。这同样可以用红蓝染色法思考。
问：有些题目，明明 m 可以是答案，但却不在初始二分区间中。比如闭区间二分初始化 right=m−1（或者开区间 right=m），这不会算错吗？
答：不会算错。注意「答案所在区间」和「二分区间」是两个概念。想一想，如果二分的 while 循环每次更新的都是 left，那么最终答案是什么？正好就是 m。一般地，如果一开始就能确定 m 一定可以满足题目要求，那么 m 是不需要在二分区间中的。换句话说，二分区间是「尚未确定是否满足题目要求」的数的范围。那些在区间外面的数，都是已确定的满足（不满足）题目要求的数。
问：什么是循环不变量？
答：想一想，对于求最小的题目，开区间二分的写法，为什么最终返回的是 right，而不是别的数？在初始化（循环之前）、循环中、循环结束后，都时时刻刻保证 check(right) == true 和 check(left) == false，这就叫循环不变量。根据循环不变量，循环结束时 left+1=right，那么 right 就是最小的满足要求的数（因为再 −1 就不满足要求了），所以答案是 right。
注：部分题目可以优化二分边界，减少二分次数，从而减少代码运行时间。对于初次接触二分答案的同学，无需强求自己写出最优的代码，设定一个比较大的二分上界也是可以的。
开区间二分模板（求最小）：
```python
class Solution:
# 计算满足 check(x) == True 的最小整数 x
def binarySearchMin(self, nums: List[int]) -> int:
# 二分猜答案：判断 mid 是否满足题目要求
def check(mid: int) -> bool:
# TODO
left = # 循环不变量：check(left) 恒为 False
right = # 循环不变量：check(right) 恒为 True
while left + 1 < right: # 开区间不为空
mid = (left + right) // 2
if check(mid): # 说明 check(>= mid 的数) 均为 True
right = mid # 接下来在 (left, mid) 中二分答案
else: # 说明 check(<= mid 的数) 均为 False
left = mid # 接下来在 (mid, right) 中二分答案
# 循环结束后 left+1 = right
# 此时 check(left) == False 而 check(left+1) == check(right) == True
# 所以 right 就是最小的满足 check 的值
return right
```
ID
Problem
Score
§2.2 求最大
一图掌握二分答案！四种写法！
在练习时，请注意「求最小」和「求最大」的二分写法上的区别。
前面的「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）。
「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别。
以开区间二分为例：
求最小：check(mid) == true 时更新 right = mid，反之更新 left = mid，最后返回 right。
求最大：check(mid) == true 时更新 left = mid，反之更新 right = mid，最后返回 left。
对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其他二分写法，开区间写法不需要思考加一减一等细节，推荐使用开区间写二分。
开区间二分模板（求最大）：
```python
class Solution:
# 计算满足 check(x) == True 的最大整数 x
def binarySearchMax(self, nums: List[int]) -> int:
# 二分猜答案：判断 mid 是否满足题目要求
def check(mid: int) -> bool:
# TODO
left = # 循环不变量：check(left) 恒为 True
right = # 循环不变量：check(right) 恒为 False
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
left = mid # 注意这里更新的是 left，和上面的模板反过来
else:
right = mid
# 循环结束后 left+1 = right
# 此时 check(left) == True 而 check(left+1) == check(right) == False
# 所以 left 就是最大的满足 check 的值
return left # check 更新的是谁，最终就返回谁
```
ID
Problem
Score
§2.3 二分间接值
二分的不是答案，而是一个和答案有关的值（间接值）。
ID
Problem
Score
§2.4 最小化最大值
本质是二分答案求最小。二分的 mid 表示上界。
好比用一个盖子（上界）去压住最大值，看看能否压住（check 函数）。
ID
Problem
Score
§2.5 最大化最小值
本质是二分答案求最大。二分的 mid 表示下界。
ID
Problem
Score
§2.6 第 K 小/大
例如数组 [1,1,1,2,2]，其中第 1 小、第 2 小和第 3 小的数都是 1，第 4 小和第 5 小的数都是 2。
第 k 小等价于：求最小的 x，满足 ≤x 的数至少有 k 个。
第 k 大等价于：求最大的 x，满足 ≥x 的数至少有 k 个。
注 1：一般规定 k 从 1 开始，而不是像数组下标那样从 0 开始。
注 2：部分题目也可以用堆解决。
ID
Problem
Score
三、三分法
ID
Problem
Score
四、其他
ID
Problem
Score
单调栈
一、单调栈
§1.1 基础
原理讲解：单调栈【基础算法精讲 26】
模板：
```python
def nearestGreater(nums: List[int]) -> Tuple[List[int], List[int]]:
n = len(nums)
# left[i] 是 nums[i] 左侧最近的严格大于 nums[i] 的数的下标，若不存在则为 -1
left = [-1] * n
st = []
for i, x in enumerate(nums):
while st and nums[st[-1]] <= x: # 如果求严格小于，改成 >=
st.pop()
if st:
left[i] = st[-1]
st.append(i)
# right[i] 是 nums[i] 右侧最近的严格大于 nums[i] 的数的下标，若不存在则为 n
right = [n] * n
st = []
for i in range(n - 1, -1, -1):
x = nums[i]
while st and nums[st[-1]] <= x:
st.pop()
if st:
right[i] = st[-1]
st.append(i)
return left, right
```
ID
Problem
Score
§1.2 进阶（选做）
ID
Problem
Score
三、贡献法
ID
Problem
Score
四、最小字典序
ID
Problem
Score
网格图
一、网格图 DFS
适用于需要计算连通块个数、大小的题目。
部分题目做法不止一种，也可以用 BFS 或并查集解决。
二叉树 DFS 与网格图 DFS 的区别：
二叉树 网格图
递归入口 根节点 网格图的某个格子
递归方向 左儿子和右儿子 一般为左右上下的相邻格子
递归边界 空节点（或者叶节点） 出界、遇到障碍或者已访问
ID
Problem
Score
二、网格图 BFS
适用于需要计算最短距离（最短路）的题目。
DFS 是不撞南墙不回头；BFS 是先访问近的，再访问远的。
ID
Problem
Score
三、网格图 0-1 BFS
边权只有 0 和 1 的题目，也可以用 BFS 做。
ID
Problem
Score
四、网格图 Dijkstra
见 图论题单 中的 Dijkstra。
五、综合应用
ID
Problem
Score
位运算
一、基础题
§1.1 基础
ID
Problem
Score
§1.2 用位运算代替数组操作
ID
Problem
Score
二、异或（XOR）的性质
本质是模 2 剩余系的加法。
ID
Problem
Score
三、与或（AND/OR）的性质
AND 的数越多，结果越小。
OR 的数越多，结果越大。
§3.1 基础
ID
Problem
Score
§3.2 AND/OR LogTrick
LogTrick 入门教程，包含原地写法，以及额外维护一个列表的写法。
模板：
```python
# 对于每个右端点 i，计算所有子数组的或值，打印这些或值的分布范围（子数组左端点范围）
# 时间复杂度 O(nlogU)，其中 U = max(nums)
def logTrick(nums: List[int]) -> None:
or_left = [] # (子数组或值，最小左端点)
for i, x in enumerate(nums):
# 计算以 i 为右端点的子数组或值
for p in or_left:
p[0] |= x # **根据题目修改**
# x 单独一个数作为子数组
or_left.append([x, i])
# 原地去重（相同或值只保留最左边的）
idx = 1
for j in range(1, len(or_left)):
if or_left[j][0] != or_left[j - 1][0]:
or_left[idx] = or_left[j]
idx += 1
del or_left[idx:]
print(i, x)
for k, (or_val, left) in enumerate(or_left):
right = or_left[k + 1][1] - 1 if k < len(or_left) - 1 else i
# 对于左端点在 [left, right]，右端点为 i 的子数组，OR 值都是 or_val
print(left, right, or_val)
```
ID
Problem
Score
§3.3 GCD LogTrick
ID
Problem
Score
四、拆位 / 贡献法
§4.1 基础
ID
Problem
Score
§4.2 十进制拆位
ID
Problem
Score
五、试填法
ID
Problem
Score
六、恒等式
ID
Problem
Score
七、线性基
模板（最大异或和）：
```python
class XorBasis:
# n 为值域最大值 U 的二进制长度，例如 U=1e9 时 n=30
def __init__(self, n: int):
self.b = [0] * n
def insert(self, x: int) -> None:
b = self.b
# 从高到低遍历，保证计算 max_xor 的时候，参与 XOR 的基的最高位（或者说二进制长度）是互不相同的
for i in range(len(b) - 1, -1, -1):
if x >> i: # 由于大于 i 的位都被我们异或成了 0，所以 x >> i 的结果只能是 0 或 1
if b[i] == 0: # x 和之前的基是线性无关的
b[i] = x # 新增一个基，最高位为 i
return
x ^= b[i] # 保证每个基的二进制长度互不相同
# 正常循环结束，此时 x=0，说明一开始的 x 可以被已有基表出，不是一个线性无关基
def max_xor(self) -> int:
b = self.b
res = 0
# 从高到低贪心：越高的位，越必须是 1
# 由于每个位的基至多一个，所以每个位只需考虑异或一个基，若能变大，则异或之
for i in range(len(b) - 1, -1, -1):
if res ^ b[i] > res: # 手写 max 更快
res ^= b[i]
return res
```
ID
Problem
Score
八、思维题
贪心、脑筋急转弯等。
ID
Problem
Score
九、其他
ID
Problem
Score
图论算法
一、图论遍历
§1.1 深度优先搜索（DFS）
找连通块、判断是否有环（如 207 题）等。部分题目做法不止一种。
模板（计算每个连通块的大小）：
Python3
Java
C++
Go
def solve(n: int, edges: List[List[int]]) -> List[int]:
# 节点编号从 0 到 n-1
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x) # 无向图
vis = [False] * n
def dfs(x: int) -> int:
vis[x] = True # 避免重复访问节点
size = 1
for y in g[x]:
if not vis[y]:
size += dfs(y)
return size
# 计算每个连通块的大小
ans = []
for i, b in enumerate(vis):
if not b: # i 没有访问过
size = dfs(i)
ans.append(size)
return ans
思维扩展：
ID
Problem
Score
§1.2 广度优先搜索（BFS）
求最短路等。要求边权都是 1（或者说都是同一个正数）。
模板（单源最短路）：
Python3
Java
C++
Go
# 计算从 start 到各个节点的最短路长度
# 如果节点不可达，则最短路长度为 -1
# 节点编号从 0 到 n-1，边权均为 1
def bfs(n: int, edges: List[List[int]], start: int) -> List[int]:
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x) # 无向图
dis = [-1] * n # -1 表示尚未访问到
dis[start] = 0
q = deque([start])
while q:
x = q.popleft()
for y in g[x]:
if dis[y] < 0:
dis[y] = dis[x] + 1
q.append(y)
return dis
ID
Problem
Score
§1.3 图论建模 + BFS 最短路
把状态抽象成图上的点，用 BFS 遍历这张图，计算从初始状态到目标状态的最短路长度。
可以锻炼状态设计能力。
ID
Problem
Score
专题：跳跃游戏
专题：跳跃游戏
注：关于网格图的 DFS 和 BFS，请看 网格图题单。
ID
Problem
Score
二、拓扑排序
§2.1 拓扑排序
模板：
Python3
Java
C++
Go
# 返回有向无环图（DAG）的其中一个拓扑序
# 如果图中有环，返回空列表
# 节点编号从 0 到 n-1
def topologicalSort(n: int, edges: List[List[int]]) -> List[int]:
g = [[] for _ in range(n)]
in_deg = [0] * n
for x, y in edges:
g[x].append(y)
in_deg[y] += 1 # 统计 y 的先修课数量
topo_order = []
q = deque(i for i, d in enumerate(in_deg) if d == 0) # 没有先修课，可以直接上
while q:
x = q.popleft()
topo_order.append(x)
for y in g[x]:
in_deg[y] -= 1 # 修完 x 后，y 的先修课数量减一
if in_deg[y] == 0: # y 的先修课全部上完
q.append(y) # 加入学习队列
if len(topo_order) < n: # 图中有环
return []
return topo_order
学习拓扑排序前，请先完成 1557. 可以到达所有点的最少点数目，有助于理解拓扑排序。
思维扩展：
ID
Problem
Score
§2.3 基环树
基环树介绍
2836. 在传球游戏中最大化函数值 2769 做法不止一种
思维扩展：
ID
Problem
Score
三、最短路
§3.1 单源最短路：Dijkstra 算法
Dijkstra 算法介绍
模板：
Python3
Java
C++
Go
# 返回从起点 start 到每个点的最短路长度 dis，如果节点 x 不可达，则 dis[x] = math.inf
# 要求：没有负数边权
# 时间复杂度 O(n + mlogm)，其中 m 是 edges 的长度。注意堆中有 O(m) 个元素
def shortestPathDijkstra(n: int, edges: List[List[int]], start: int) -> List[int]:
# 注：如果节点编号从 1 开始（而不是从 0 开始），可以把 n 加一
g = [[] for _ in range(n)] # 邻接表
for x, y, wt in edges:
g[x].append((y, wt))
# g[y].append((x, wt)) # 无向图加上这行
dis = [inf] * n
dis[start] = 0 # 起点到自己的距离是 0
h = [(0, start)] # 堆中保存 (起点到节点 x 的最短路长度，节点 x)
while h:
dis_x, x = heappop(h)
if dis_x > dis[x]: # x 之前出堆过
continue
for y, wt in g[x]:
new_dis_y = dis_x + wt
if new_dis_y < dis[y]:
dis[y] = new_dis_y # 更新 x 的邻居的最短路
# 懒更新堆：只插入数据，不更新堆中数据
# 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
heappush(h, (new_dis_y, y))
return dis
分层图最短路：
SPFA 与差分约束：
力扣上的 SPFA 题很少。
ID
Problem
Score
§3.2 全源最短路：Floyd 算法
Floyd 算法本质是三维 DP。
带你发明 Floyd 算法：从记忆化搜索到递推
模板：
Python3
Java
C++
Go
# 返回一个二维列表，其中 (i,j) 这一项表示从 i 到 j 的最短路长度
# 如果无法从 i 到 j，则最短路长度为 math.inf
# 允许负数边权
# 如果计算完毕后，存在 i，使得从 i 到 i 的最短路长度小于 0，说明图中有负环
# 节点编号从 0 到 n-1
# 时间复杂度 O(n^3 + m)，其中 m 是 edges 的长度
def shortestPathFloyd(self, n: int, edges: List[List[int]]) -> List[List[int]]:
f = [[inf] * n for _ in range(n)]
for i in range(n):
f[i][i] = 0
for x, y, wt in edges:
f[x][y] = min(f[x][y], wt) # 如果有重边，取边权最小值
f[y][x] = min(f[y][x], wt) # 无向图
for k in range(n):
for i in range(n):
if f[i][k] == inf: # 针对稀疏图的优化
continue
for j in range(n):
f[i][j] = min(f[i][j], f[i][k] + f[k][j])
return f
Bitset 优化 Floyd
ID
Problem
Score
四、最小生成树
四、最小生成树
思维扩展
ID
Problem
Score
六、强连通分量/双连通分量
六、强连通分量/双连通分量
ID
Problem
Score
八、网络流
八、网络流
模拟费用流
ID
Problem
Score
九、其他
九、其他
1
∣+∣s
2
∣)
ID
Problem
Score
动态规划
一、入门 DP
§1.1 爬楼梯
讲解
ID
Problem
Score
§1.2 打家劫舍
答疑
问：在 1:1 翻译的过程中，如何根据记忆化搜索，确定递推数组（DP 数组）的大小？为什么有时候要开 n+1 大小的数组，有时候要开 n+2 大小的数组？
答：看记忆化搜索的参数的范围（最小值和最大值）。例如 i 最小是 −1（递归边界也算），最大是 n−1（递归入口），那么一共有 n+1 个不同的 i，就需要开 n+1 大小的 DP 数组。如果 i 最小是 −2，最大是 n−1，一共有 n+2 个不同的 i，就需要开 n+2 大小的 DP 数组。
思维扩展：
ID
Problem
Score
§1.3 最大子数组和（最大子段和）
有两种做法：
定义状态 f[i] 表示以 a[i] 结尾的最大子数组和，不和 i 左边拼起来就是 f[i]=a[i]，和 i 左边拼起来就是 f[i]=f[i−1]+a[i]，取最大值就得到了状态转移方程 f[i]=max(f[i−1],0)+a[i]，答案为 max(f)。这个做法也叫做 Kadane 算法。
用 前缀和，转化成 121. 买卖股票的最佳时机。
思维扩展：
思考题
完成本章后，请思考：什么时候要返回 f[n]，什么时候要返回 max(f)？
ID
Problem
Score
二、网格图 DP
§2.1 基础
思维扩展：
ID
Problem
Score
§2.2 进阶
ID
Problem
Score
三、背包
§3.1 0-1 背包
每个物品只能选一次，即要么选，要么不选。
所以 0-1 背包是「选或不选」的代表。关于「枚举选哪个」的代表，见本题单的「§4.2 最长递增子序列」。
进阶：
ID
Problem
Score
§3.2 完全背包
物品可以重复选，无个数限制。
思维扩展：
ID
Problem
Score
§3.3 多重背包（选做）
物品可以重复选，有个数限制。
求方案数
注意求方案数的题目不能用二进制优化。比如从 6 个相同物品中选 3 个，只有一种选法。但按照二进制优化，会把 6 分解为 1+2+3，有 1+2 和 3 两种选法。
如果要优化，可以考虑用 同余前缀和 优化。
二进制优化
ID
Problem
Score
§3.4 分组背包
同一组内的物品至多/恰好选一个。
ID
Problem
Score
§3.5 树形背包（选做）
也叫树上背包、依赖背包等。
注：目前力扣只有无依赖的背包，时间复杂度为 O(nW
2
)。如果有依赖，可以优化到 O(nW)。
ID
Problem
Score
四、经典线性 DP
§4.1 最长公共子序列（LCS）
讲解：最长公共子序列 编辑距离【基础算法精讲 19】
一般定义 f[i][j] 表示对 (s[:i],t[:j]) 的求解结果。
§4.1.1 基础
思维扩展：
ID
Problem
Score
§4.1.2 进阶
思考题：
115 题的扩展。给定字符串 s 和 t，你可以在 s 的任意位置插入一个字母，插入后，s 最多有多少个子序列等于 t？
思路和代码见 评论。
ID
Problem
Score
§4.2 最长递增子序列（LIS）
讲解：最长递增子序列【基础算法精讲 20】
做法有很多：
枚举选哪个。（见讲解）
二分。（见讲解）
计算 a 和把 a 排序后的数组 sortedA 的最长公共子序列。（用 LCS 求 LIS）
数据结构优化。（见 2407 题）
§4.2.1 基础
ID
Problem
Score
§4.2.2 进阶
思维扩展：
思考题：
给定整数 k，构造一个数组 a，使得 a 恰好有 k 个最长递增子序列。
解答（评论）
ID
Problem
Score
五、划分型 DP
§5.1 判定能否划分
一般定义 f[i] 表示长为 i 的前缀 a[:i] 能否划分。
枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 是否满足要求。
ID
Problem
Score
§5.2 最优划分
计算最少（最多）可以划分出多少段、最优划分得分等。
一般定义 f[i] 表示长为 i 的前缀 a[:i] 在题目约束下，分割出的最少（最多）子数组个数（或者定义成分割方案数）。
枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 对最优解的影响。
2
)
ID
Problem
Score
§5.3 约束划分个数
将数组分成（恰好/至多）k 个连续子数组，计算与这些子数组有关的最优值。
一般定义 f[i][j] 表示将长为 j 的前缀 a[:j] 分成 i 个连续子数组所得到的最优解。
枚举最后一个子数组的左端点 L，从 f[i−1][L] 转移到 f[i][j]，并考虑 a[L:j] 对最优解的影响。
注：对于恰好型划分 DP，可以通过控制内层循环的上下界，把时间复杂度从 O(nk) 优化至 O((n−k)k)。例如 3473 题。
ID
Problem
Score
六、状态机 DP
§6.1 买卖股票
讲解【基础算法精讲 21】
ID
Problem
Score
§6.2 基础
ID
Problem
Score
§6.3 进阶
ID
Problem
Score
七、其他线性 DP
§7.1 一维 DP
发生在前缀/后缀之间的转移，例如从 f[i−1] 转移到 f[i]，或者从 f[j] 转移到 f[i]。
ID
Problem
Score
§7.2 不相交区间
ID
Problem
Score
§7.3 子数组 DP
思维扩展：
ID
Problem
Score
§7.4 合法子序列 DP
计算合法子序列的最长长度、个数、元素和等。
一般定义 f[x] 表示以元素 x 结尾的合法子序列的最长长度/个数/元素和，从子序列的倒数第二个数转移过来。
注意这里的 x 不是下标，是元素值。如果 x 不是整数，或者值域范围很大，可以用哈希表代替数组。
思维扩展：
ID
Problem
Score
§7.5 子矩形 DP
ID
Problem
Score
§7.6 多维 DP
不会设计状态？那你可要好好刷这一节了。
2
)
思维扩展：
ID
Problem
Score
八、区间 DP
§8.1 最长回文子序列
ID
Problem
Score
§8.2 区间 DP
对于类似合法括号字符串（RBS）的消除问题，通常根据题意，会有如下性质：
可以消除相邻的匹配字符。
相邻匹配字符消除后，原本不相邻的字符会变成相邻，可以继续消除。换句话说，设子串 A=x+B+y，如果 x 和 y 是匹配的（可以消除），且子串 B 可以完全消除，那么子串 A 可以完全消除。
设子串 A=B+C，如果子串 B 和 C 可以完全消除，那么子串 A 可以完全消除。
满足上述性质的题目（例如 3563 题），可以用区间 DP 解决。
定义 f(i,j) 表示消除 s[i] 到 s[j] 的最优值。
根据性质 2，可以把 f(i,j) 缩小成子问题 f(i+1,j−1)。
根据性质 3，可以枚举子串 B 的右端点，即枚举 k=i+1,i+3,i+5,…,j−2，把 f(i,j) 划分成子问题 f(i,k) 和 f(k+1,j)。注意这里枚举 k 的步长是 2，因为每次消除 2 个字符，被消除的子串长度一定是偶数。
边界：f(i+1,i)，即空串。
答案：f(0,n−1)。
ID
Problem
Score
九、状态压缩 DP（状压 DP）
§9.1 排列型状压 DP ① 相邻无关
学习指南：
从集合论到位运算，常见位运算技巧分类总结
教你一步步思考状压 DP：从记忆化搜索到递推
暴力做法是枚举所有排列，对每个排列计算和题目有关的值，时间复杂度（通常来说）是 O(n!)。可以解决 n≤10 的问题。
状压 DP 可以把时间复杂度（通常来说）优化至 O(n⋅2
n
)。可以解决 n≤20 的问题。
一般有两种定义方式：
定义 f[S] 表示已经排列好的元素（下标）集合为 S 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。
定义 f[S] 表示可以选的元素（下标）集合为 S 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。
注：部分题目由于暴搜+剪枝也能过，难度分仅供参考。
ID
Problem
Score
§9.2 排列型状压 DP ② 相邻相关
一般定义 f[S][i] 表示未选（或者已选）的集合为 S，且上一个填的元素（下标）为 i 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。
时间复杂度（通常来说）是 O(n
2
⋅2
n
)。
ID
Problem
Score
§9.3 旅行商问题（TSP）
本质上就是排列型 ②。
相似问题：
ID
Problem
Score
§9.4 子集状压 DP
一般定义 f[S] 表示未选（或者已选）的集合为 S 时，和题目有关的最优值。通过枚举 S（或者 S 的补集 ∁
U
S）的子集来转移。
时间复杂度（通常来说）是 O(3
n
)，证明：
对于大小为 n 的集合，它的大小为 m 的子集有 (
m
n
) 个，每个子集又有 2
m
个子集。根据二项式定理，
m=0
∑
n
(
m
n
)2
m
=(2+1)
n
=3
n
，所以「枚举子集的子集」的总体时间复杂度为 O(3
n
)。
值得注意的是，枚举子集的子集还可以用「选或不选」来做，对于存在无效状态的情况，可以做到更优的时间复杂度。具体见 1349 题解 最后的写法。
2
⋅2
n
) 做法
相关问题：
ID
Problem
Score
§9.5 SOS DP
子集和 DP（Sum Over Subsets DP，SOS DP），国内算法竞赛圈一般叫高维前缀和。
原理讲解（方法二）
模板（从子集转移过来）：
Python3
Java
C++
Go
# 设 w 为 a[i] 的二进制最大长度
# 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的子集的元素个数（把二进制数视作集合）
# 时间复杂度 O(n + U log U)，其中 U = max(a)
def sos_dp(a: List[int]) -> List[int]:
mx = max(a)
w = mx.bit_length() # 二进制长度上限
u = 1 << w
f = [0] * u
for x in a:
f[x] += 1 # 初始值
for i in range(w):
bit = 1 << i
s = 0
while s < u:
s |= bit # 优化：快速跳到 i 位是 1 的 s
f[s] += f[s ^ bit]
s += 1
return f
模板（从超集转移过来）：
Python3
Java
C++
Go
# 设 w 为 a[i] 的二进制最大长度
# 返回一个长为 2^w 的数组 f，其中 f[S] 表示 a 中是 S 的超集的元素个数（把二进制数视作集合）
# 时间复杂度 O(n + U log U)，其中 U = max(a)
def sos_dp(a: List[int]) -> List[int]:
mx = max(a)
w = mx.bit_length() # 二进制长度上限
u = 1 << w
f = [0] * u
for x in a:
f[x] += 1 # 初始值
for i in range(w):
bit = 1 << i
s = 0
while s < u:
s |= bit # 优化：快速跳到 i 位是 1 的 s
f[s ^ bit] += f[s]
s += 1
return f
ID
Problem
Score
§9.6 其他状压 DP
ID
Problem
Score
十、数位 DP
§10.1 统计合法元素的数目
数位 DP v1.0 模板讲解
数位 DP v2.0 模板讲解（上下界数位 DP）
下面是数位 DP v2.1 模板。相比 v2.0，不需要写 isNum 参数。
注：只有上界约束的题目，相当于 low=0 或者 low=1。
Python3
Java
C++
Go
# 代码示例：返回 [low, high] 中的恰好包含 target 个 0 的数字个数
# 比如 digitDP(0, 10, 1) == 2
# 要点：我们统计的是 0 的个数，需要区分【前导零】和【数字中的零】，前导零不能计入，而数字中的零需要计入
def digitDP(low: int, high: int, target: int) -> int:
low_s = list(map(int, str(low))) # 避免在 dfs 中频繁调用 int()
high_s = list(map(int, str(high)))
n = len(high_s)
diff_lh = n - len(low_s)
@cache
def dfs(i: int, cnt0: int, limit_low: bool, limit_high: bool) -> int:
if cnt0 > target:
return 0 # 不合法
if i == n:
return 1 if cnt0 == target else 0
lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
hi = high_s[i] if limit_high else 9
res = 0
start = lo
# 通过 limit_low 和 i 可以判断能否不填数字，无需 is_num 参数
# 如果前导零不影响答案，去掉这个 if block
if limit_low and i < diff_lh:
# 不填数字，上界不受约束
res = dfs(i + 1, 0, True, False)
start = 1
for d in range(start, hi + 1):
res += dfs(i + 1,
cnt0 + (1 if d == 0 else 0), # 统计 0 的个数
limit_low and d == lo,
limit_high and d == hi)
# res %= MOD
return res
return dfs(0, 0, True, True)
从低到高：
ID
Problem
Score
§10.2 统计合法元素的价值总和
每个元素 x 都有一个相应的价值 f(x)，计算 [low,high] 中的满足题目约束的元素的价值总和。
例如 f(x)=x 是计算满足题目约束的元素和，f(x)=digsum(x) 是计算满足题目约束的元素的数位和。
模板（数位和）：
Python3
Java
C++
Go
# 计算在 [low, high] 中的整数 x 的数位和，满足 x 中的不同数字个数不超过 k
def digitDPContribution(low: int, high: int, k: int) -> int:
low_s = list(map(int, str(low))) # 避免在 dfs 中频繁调用 int()
high_s = list(map(int, str(high)))
n = len(high_s)
diff_lh = n - len(low_s)
# dfs 返回两个数：子树合法数字个数，子树数位总和
@cache
def dfs(i: int, mask: int, limit_low: bool, limit_high: bool) -> Tuple[int, int]:
if i == n:
# 如果没有特殊约束，那么能递归到终点的都是合法数字
return 1, 0
lo = low_s[i - diff_lh] if limit_low and i >= diff_lh else 0
hi = high_s[i] if limit_high else 9
cnt = res = 0
start = lo
# 如果前导零不影响答案，去掉这个 if block
if limit_low and i < diff_lh:
# 不填数字，上界不受约束
cnt, res = dfs(i + 1, 0, True, False)
start = 1
for d in range(start, hi + 1):
new_mask = mask | 1 << d
if new_mask.bit_count() > k: # 不满足要求
continue
sub_cnt, sub_sum = dfs(i + 1,
new_mask,
limit_low and d == lo,
limit_high and d == hi)
cnt += sub_cnt # 累加子树的合法数字个数
res += sub_sum # 累加子树的数位总和
res += d * sub_cnt # d 会出现在 sub_cnt 个数中（贡献法）
# cnt %= MOD; res %= MOD
return cnt, res
return dfs(0, 0, True, True)[1]
ID
Problem
Score
§10.3 其他数位 DP
ID
Problem
Score
十一、优化 DP
§11.1 前缀和优化 DP
ID
Problem
Score
§11.2 单调栈优化 DP
前置题单：单调栈（矩形系列/字典序最小/贡献法）
ID
Problem
Score
§11.3 单调队列优化 DP
一般用来维护一段转移来源的最值。
前提：区间右端点变大时，左端点也在变大（同滑动窗口）。
转移前，去掉队首无用数据。
计算转移（直接从队首转移）。
把数据（一般是 f[i]）插入队尾前，去掉队尾无用数据。
2
)
ID
Problem
Score
§11.4 树状数组/线段树优化 DP
ID
Problem
Score
§11.5 字典树优化 DP
ID
Problem
Score
§11.6 矩阵快速幂优化 DP
有两种类型的矩阵快速幂优化 DP：
线性 DP（常系数齐次线性递推），转移系数写在第一行，其余行 m
i+1,i
=1，例如 70， 1137。讲解。
多维 DP 或者状态机 DP，转移系数可表示为一个 k×k 大小的矩阵，例如 935。讲解。
时间复杂度一般为 O(k
3
logn)。
进阶做法：先用 Berlekamp-Massey 算法找规律，得到线性递推式，然后用 Kitamasa 算法（或者 Bostan-Mori 算法）优化。
请看我的知乎科普文章：
Berlekamp-Massey 算法：如何预测数列的下一项？
Kitamasa 算法：更快地计算线性递推的第 n 项
具体例子见 3700 题 我的题解的方法二。
时间复杂度一般为 O(k
2
logn)。
ID
Problem
Score
§11.7 斜率优化 DP
也叫凸包优化/凸壳优化（CHT，Convex Hull Trick）。
ID
Problem
Score
§11.8 WQS 二分优化 DP
把最多选 k 个物品的问题（时间复杂度高）转换成选任意个物品的问题（时间复杂度低）。
一般时间复杂度为 O(nlogU) 或者 O(nlogn)。
此外「§5.3 约束划分个数」的部分题目也可以用 WQS 二分优化。
ID
Problem
Score
§11.9 其他优化 DP
关于倍增算法，见 题单 的「§3.8 最近公共祖先（LCA）、倍增算法」。
ID
Problem
Score
十二、树形 DP
§12.1 树的直径
讲解：树形 DP：树的直径【基础算法精讲 23】
注：求直径也有两次 DFS 的做法。
ID
Problem
Score
§12.2 树上最大独立集
讲解：树形 DP：打家劫舍 III【基础算法精讲 24】
ID
Problem
Score
§12.3 树上最小支配集
讲解：树形 DP：监控二叉树【基础算法精讲 25】，包含 968 的变形题。
ID
Problem
Score
§12.4 换根 DP
也叫二次扫描法。
【图解】一张图秒懂换根 DP！
注：前后缀分解，可以视作一条链上的换根 DP。
ID
Problem
Score
§12.5 其他树形 DP
ID
Problem
Score
十三、图 DP
十三、图 DP
另见【题单】图论算法 中的「全源最短路：Floyd」，本质是多维 DP。
ID
Problem
Score
十四、博弈 DP
十四、博弈 DP
ID
Problem
Score
专题：输出具体方案（打印方案）
专题：输出具体方案（打印方案）
ID
Problem
Score
专题：前后缀分解
专题：前后缀分解
补充题目：
输入一个长为 n 的 prices 数组，你需要返回一个长为 n 的 answer 数组，其中 answer[i] 表示删除 prices[i]，也就是禁止在第 i 天买卖股票，在此约束下 🕓 121. 买卖股票的最佳时机 的答案。
ID
Problem
Score
专题：把 X 变成 Y
专题：把 X 变成 Y
另见 图论题单 中的 Dijkstra 算法，例如：
ID
Problem
Score
其他
其他
ID
Problem
Score
常用数据结构
一、前缀和
§1.1 基础
讲解
左闭右开公式：子数组 [left,right) 的元素和为 sum[right]−sum[left]。把下标区间定义成左闭右开，就不需要加一减一了。
思维扩展：
ID
Problem
Score
§1.2 前缀和与哈希表
通常要用到「枚举右，维护左」的技巧。
讲解
前缀和与有序集合：
思维扩展：
ID
Problem
Score
§1.3 距离和
图解
ID
Problem
Score
§1.4 状态压缩前缀和
推荐先阅读：从集合论到位运算，常见位运算技巧分类总结！
ID
Problem
Score
§1.5 进阶
思维扩展：
ID
Problem
Score
二、差分
§2.1 一维差分
差分与前缀和的关系，类似导数与积分的关系。
数组 a 的差分的前缀和就是数组 a（不变）。
原理讲解
§2.1.2 进阶
思维扩展：
ID
Problem
Score
三、栈
§3.2 进阶
ID
Problem
Score
§3.3 邻项消除
ID
Problem
Score
§3.4 合法括号字符串（RBS）
注：部分题目可以不用栈，而是用一个数字记录嵌套深度。
ID
Problem
Score
§3.5 表达式解析
ID
Problem
Score
§3.6 对顶栈
ID
Problem
Score
§3.7 单调栈
见 单调栈题单。
四、队列
§4.1 基础
ID
Problem
Score
§4.3 双端队列
ID
Problem
Score
§4.4 单调队列
个人觉得叫单调双端队列更准确。
单调队列 = 滑动窗口 + 单调栈。必须先掌握滑动窗口和单调栈这两个知识点，再学单调队列。
问：入队、出队、更新答案，这三步的顺序如何思考？
答：有两种情况。如果更新答案时，用到的数据包含当前元素，那么就需要先入队，再更新答案；如果用到的数据不包含当前元素，那么就需要先更新答案，再入队。至于出队，一般写在前面，每遍历到一个新的元素，就看看队首元素是否失效（不满足要求），失效则弹出队首。
原理讲解
模板：
Python3
Java
C++
Go
# 计算 nums 的每个长为 k 的窗口的最大值
# 时间复杂度 O(n)，其中 n 是 nums 的长度
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
ans = [0] * (len(nums) - k + 1) # 窗口个数
q = deque() # 双端队列
for i, x in enumerate(nums):
# 1. 右边入
while q and nums[q[-1]] <= x:
q.pop() # 维护 q 的单调性
q.append(i) # 注意保存的是下标，这样下面可以判断队首是否离开窗口
# 2. 左边出
left = i - k + 1 # 窗口左端点
if q[0] < left: # 队首离开窗口
q.popleft()
# 3. 在窗口左端点处记录答案
if left >= 0:
# 由于队首到队尾单调递减，所以窗口最大值就在队首
ans[left] = nums[q[0]]
return ans
关于单调队列优化 DP，见 动态规划题单 中的「§11.3 单调队列优化 DP」。
ID
Problem
Score
五、堆（优先队列）
§5.1 基础
为什么堆化的时间复杂度是 O(n)？
ID
Problem
Score
§5.2 进阶
有序集合：
ID
Problem
Score
§5.5 反悔堆
基于堆的反悔贪心。
ID
Problem
Score
§5.6 懒删除堆
支持删除堆中任意元素。
模板：
Python3
Java
C++
Go
# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
class LazyHeap:
def __init__(self):
self.heap = [] # 最小堆（最大堆可以把数字取反或重载 __lt__）
self.remove_cnt = defaultdict(int) # 每个元素剩余需要删除的次数
self.size = 0 # 堆的实际大小
# 删除
def remove(self, x: Any) -> None:
self.remove_cnt[x] += 1 # 懒删除
self.size -= 1
# 正式执行删除操作
def _apply_remove(self) -> None:
while self.heap and self.remove_cnt[self.heap[0]] > 0:
self.remove_cnt[self.heap[0]] -= 1
heappop(self.heap)
# 查看堆顶
def top(self) -> Any:
self._apply_remove()
return self.heap[0] # 真正的堆顶
# 出堆
def pop(self) -> Any:
self._apply_remove()
self.size -= 1
return heappop(self.heap)
# 入堆
def push(self, x: Any) -> None:
if self.remove_cnt[x] > 0:
self.remove_cnt[x] -= 1 # 抵消之前的删除
else:
heappush(self.heap, x)
self.size += 1
ID
Problem
Score
§5.7 对顶堆（滑动窗口第 K 小/大）
讲解
部分题目需要结合懒删除堆。
另见 图论题单 中的 Dijkstra 算法。
ID
Problem
Score
六、字典树（trie）
§6.2 进阶
思维扩展：
ID
Problem
Score
§6.3 字典树优化 DP
ID
Problem
Score
§6.4 0-1 字典树（异或字典树）
部分题目也可以用试填法解决。
ID
Problem
Score
七、并查集
§7.1 基础
更多基础题，见 网格图题单 中的 DFS 和 图论题单 中的 DFS，其中大部分题目也可以用并查集实现。
ID
Problem
Score
§7.2 进阶
另见 图论题单 中的最小生成树。
ID
Problem
Score
§7.3 GCD 并查集
ID
Problem
Score
§7.4 数组上的并查集
ID
Problem
Score
§7.5 区间并查集
ID
Problem
Score
§7.6 带权并查集（边权并查集）
模板：
Python3
Java
C++
Go
# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
class UnionFind:
def __init__(self, n: int):
# 一开始有 n 个集合 {0}, {1}, ..., {n-1}
# 集合 i 的代表元是自己，自己到自己的距离是 0
self.fa = list(range(n)) # 代表元
self.dis = [0] * n # dis[x] 表示 x 到（x 所在集合的）代表元的距离
# 返回 x 所在集合的代表元
# 同时做路径压缩
def find(self, x: int) -> int:
fa = self.fa
if fa[x] != x:
root = self.find(fa[x])
self.dis[x] += self.dis[fa[x]] # 递归更新 x 到其代表元的距离
fa[x] = root
return fa[x]
# 判断 x 和 y 是否在同一个集合（同普通并查集）
def same(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
# 计算从 from 到 to 的相对距离
# 调用时需保证 from 和 to 在同一个集合中，否则返回值无意义
def get_relative_distance(self, from_: int, to: int) -> int:
self.find(from_)
self.find(to)
# to-from = (x-from) - (x-to) = dis[from] - dis[to]
return self.dis[from_] - self.dis[to]
# 合并 from 和 to，新增信息 to - from = value
# 其中 to 和 from 表示未知量，下文的 x 和 y 也表示未知量
# 如果 from 和 to 不在同一个集合，返回 True，否则返回是否与已知信息矛盾
def merge(self, from_: int, to: int, value: int) -> bool:
x, y = self.find(from_), self.find(to)
dis = self.dis
if x == y: # from 和 to 在同一个集合，不做合并
# to-from = (x-from) - (x-to) = dis[from] - dis[to] = value
return dis[from_] - dis[to] == value
# x --------- y
# / /
# from ------- to
# 已知 x-from = dis[from] 和 y-to = dis[to]，现在合并 from 和 to，新增信息 to-from = value
# 由于 y-from = (y-x) + (x-from) = (y-to) + (to-from)
# 所以 y-x = (to-from) + (y-to) - (x-from) = value + dis[to] - dis[from]
dis[x] = value + dis[to] - dis[from_] # 计算 x 到其代表元 y 的距离
self.fa[x] = y
return True
附加模板题：CF1850H
ID
Problem
Score
八、树状数组和线段树
§8.1 树状数组
讲解：带你发明树状数组！附数学证明
模板：
Python3
Java
C++
Go
# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
class FenwickTree:
def __init__(self, n: int):
self.tree = [0] * (n + 1) # 使用下标 1 到 n
# a[i] 增加 val
# 1 <= i <= n
# 时间复杂度 O(log n)
def update(self, i: int, val: int) -> None:
t = self.tree
while i < len(t):
t[i] += val
i += i & -i
# 计算前缀和 a[1] + ... + a[i]
# 1 <= i <= n
# 时间复杂度 O(log n)
def pre(self, i: int) -> int:
t = self.tree
res = 0
while i > 0:
res += t[i]
i &= i - 1
return res
# 计算区间和 a[l] + ... + a[r]
# 1 <= l <= r <= n
# 时间复杂度 O(log n)
def query(self, l: int, r: int) -> int:
if r < l:
return 0
return self.pre(r) - self.pre(l - 1)
ID
Problem
Score
§8.2 逆序对
除了可以用树状数组解决，部分题目也可以在归并排序的同时计算。
ID
Problem
Score
§8.3 线段树（无区间更新）
线段树本质是二叉树，在学习之前，建议先做做 104. 二叉树的最大深度 和 111. 二叉树的最小深度（自底向上写法），当作热身。
线段树：为什么要这样设计？ 理解线段树发明的动机。
把任意区间用 O(logn) 个区间表示，线段树的每个节点记录对应区间的信息。
询问：把询问区间拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点，把这 O(logn) 个节点的信息合并，即为答案。
单点更新：有 O(logn) 个区间包含被修改的位置，需要更新 O(logn) 个节点的信息。
基础模板代码如下。为方便入门理解，我没有做复杂封装。通用模板代码可以参考 AtCoder Library 的 segtree.hpp。
Python3
Java
C++
Go
# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
# 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
# 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
# 区间的下标：从 0 开始
class SegmentTree:
def __init__(self, arr, default=0):
# 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
# arr 可以是 list 或者 int
# 如果 arr 是 int，视作数组大小，默认值为 default
if isinstance(arr, int):
arr = [default] * arr
n = len(arr)
self._n = n
self._tree = [0] * (2 << (n - 1).bit_length())
self._build(arr, 1, 0, n - 1)
# 合并两个 val
def _merge_val(self, a: int, b: int) -> int:
return max(a, b) # **根据题目修改**
# 合并左右儿子的 val 到当前节点的 val
def _maintain(self, node: int) -> None:
self._tree[node] = self._merge_val(self._tree[node * 2], self._tree[node * 2 + 1])
# 用 a 初始化线段树
# 时间复杂度 O(n)
def _build(self, a: List[int], node: int, l: int, r: int) -> None:
if l == r: # 叶子
self._tree[node] = a[l] # 初始化叶节点的值
return
m = (l + r) // 2
self._build(a, node * 2, l, m) # 初始化左子树
self._build(a, node * 2 + 1, m + 1, r) # 初始化右子树
self._maintain(node)
def _update(self, node: int, l: int, r: int, i: int, val: int) -> None:
if l == r: # 叶子（到达目标）
# 如果想直接替换的话，可以写 self._tree[node] = val
self._tree[node] = self._merge_val(self._tree[node], val)
return
m = (l + r) // 2
if i <= m: # i 在左子树
self._update(node * 2, l, m, i, val)
else: # i 在右子树
self._update(node * 2 + 1, m + 1, r, i, val)
self._maintain(node)
def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
if ql <= l and r <= qr: # 当前子树完全在 [ql, qr] 内
return self._tree[node]
m = (l + r) // 2
if qr <= m: # [ql, qr] 在左子树
return self._query(node * 2, l, m, ql, qr)
if ql > m: # [ql, qr] 在右子树
return self._query(node * 2 + 1, m + 1, r, ql, qr)
l_res = self._query(node * 2, l, m, ql, qr)
r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
return self._merge_val(l_res, r_res)
# 更新 a[i] 为 _merge_val(a[i], val)
# 时间复杂度 O(log n)
def update(self, i: int, val: int) -> None:
self._update(1, 0, self._n - 1, i, val)
# 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
# 时间复杂度 O(log n)
def query(self, ql: int, qr: int) -> int:
return self._query(1, 0, self._n - 1, ql, qr)
# 获取 a[i] 的值
# 时间复杂度 O(log n)
def get(self, i: int) -> int:
return self._query(1, 0, self._n - 1, i, i)
思维扩展：
ID
Problem
Score
§8.4 Lazy 线段树（有区间更新）
把任意区间用 O(logn) 个区间表示，线段树的每个节点记录对应区间的信息。
询问：把询问区间拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点，把这 O(logn) 个节点的信息合并，即为答案。
区间更新：仍然是拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点。但对于其中的非叶节点，不把更新的内容往下传递给子节点，而是记录「发生了更新，内容为 xxx」，把更新的内容记录下来。直到后续的询问或更新操作，需要访问或修改更下面的子节点信息时，才把更新的内容往下传。
基础模板代码如下。为方便入门理解，我没有做复杂封装。通用模板代码可以参考 AtCoder Library 的 lazysegtree.hpp。
Python3
Java
C++
Go
# 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
class Node:
__slots__ = 'val', 'todo'
class LazySegmentTree:
# 懒标记初始值
_TODO_INIT = 0 # **根据题目修改**
def __init__(self, arr, default=0):
# 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
# arr 可以是 list 或者 int
# 如果 arr 是 int，视作数组大小，默认值为 default
if isinstance(arr, int):
arr = [default] * arr
n = len(arr)
self._n = n
self._tree = [Node() for _ in range(2 << (n - 1).bit_length())]
self._build(arr, 1, 0, n - 1)
# 合并两个 val
def _merge_val(self, a: int, b: int) -> int:
return a + b # **根据题目修改**
# 合并两个懒标记
def _merge_todo(self, a: int, b: int) -> int:
return a + b # **根据题目修改**
# 把懒标记作用到 node 子树（本例为区间加）
def _apply(self, node: int, l: int, r: int, todo: int) -> None:
cur = self._tree[node]
# 计算 tree[node] 区间的整体变化
cur.val += todo * (r - l + 1) # **根据题目修改**
cur.todo = self._merge_todo(todo, cur.todo)
# 把当前节点的懒标记下传给左右儿子
def _spread(self, node: int, l: int, r: int) -> None:
todo = self._tree[node].todo
if todo == self._TODO_INIT: # 没有需要下传的信息
return
m = (l + r) // 2
self._apply(node * 2, l, m, todo)
self._apply(node * 2 + 1, m + 1, r, todo)
self._tree[node].todo = self._TODO_INIT # 下传完毕
# 合并左右儿子的 val 到当前节点的 val
def _maintain(self, node: int) -> None:
self._tree[node].val = self._merge_val(self._tree[node * 2].val, self._tree[node * 2 + 1].val)
# 用 a 初始化线段树
# 时间复杂度 O(n)
def _build(self, a: List[int], node: int, l: int, r: int) -> None:
self._tree[node].todo = self._TODO_INIT
if l == r: # 叶子
self._tree[node].val = a[l] # 初始化叶节点的值
return
m = (l + r) // 2
self._build(a, node * 2, l, m) # 初始化左子树
self._build(a, node * 2 + 1, m + 1, r) # 初始化右子树
self._maintain(node)
def _update(self, node: int, l: int, r: int, ql: int, qr: int, f: int) -> None:
if ql <= l and r <= qr: # 当前子树完全在 [ql, qr] 内
self._apply(node, l, r, f)
return
self._spread(node, l, r)
m = (l + r) // 2
if ql <= m: # 更新左子树
self._update(node * 2, l, m, ql, qr, f)
if qr > m: # 更新右子树
self._update(node * 2 + 1, m + 1, r, ql, qr, f)
self._maintain(node)
def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
if ql <= l and r <= qr: # 当前子树完全在 [ql, qr] 内
return self._tree[node].val
self._spread(node, l, r)
m = (l + r) // 2
if qr <= m: # [ql, qr] 在左子树
return self._query(node * 2, l, m, ql, qr)
if ql > m: # [ql, qr] 在右子树
return self._query(node * 2 + 1, m + 1, r, ql, qr)
l_res = self._query(node * 2, l, m, ql, qr)
r_res = self._query(node * 2 + 1, m + 1, r, ql, qr)
return self._merge_val(l_res, r_res)
# 用 f 更新 [ql, qr] 中的每个 a[i]
# 0 <= ql <= qr <= n-1
# 时间复杂度 O(log n)
def update(self, ql: int, qr: int, f: int) -> None:
self._update(1, 0, self._n - 1, ql, qr, f)
# 返回用 _merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
# 0 <= ql <= qr <= n-1
# 时间复杂度 O(log n)
def query(self, ql: int, qr: int) -> int:
return self._query(1, 0, self._n - 1, ql, qr)
ID
Problem
Score
§8.5 动态开点线段树
部分题目也可以用珂朵莉树解决。
ID
Problem
Score
§8.6 ST 表（Sparse Table）
ST 表 支持区间最值查询（Range Minimum/Maximum Query，RMQ），但不支持修改。
优点是代码短，且查询的时间复杂度是 O(1)。所以作为补充内容，附在此处。
Python3
Java
C++
Go
class SparseTable:
# 时间复杂度 O(n * log n)
def __init__(self, nums: List[int], op: Callable[[int, int], int]):
n = len(nums)
w = n.bit_length()
st = [[0] * n for _ in range(w)]
st[0] = nums[:]
for i in range(1, w):
for j in range(n - (1 << i) + 1):
st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))])
self.st = st
self.op = op
# [l, r) 左闭右开，下标从 0 开始
# 返回 op(nums[l:r])
# 时间复杂度 O(1)
def query(self, l: int, r: int) -> int:
k = (r - l).bit_length() - 1
return self.op(self.st[k][l], self.st[k][r - (1 << k)])
# 使用方法举例
nums = [3, 1, 4, 1, 5, 9, 2, 6]
st = SparseTable(nums, max)
print(st.query(0, 5)) # max(nums[0:5]) = 5
print(st.query(1, 1)) # 错误：必须保证 l < r
ID
Problem
Score
九、伸展树（Splay 树）
ID
Problem
Score
十、根号算法
§8.1 根号分解（Sqrt Decomposition）
ID
Problem
Score
§8.2 莫队算法
属于离线算法的一种。
ID
Problem
Score
§8.3 其他
ID
Problem
Score
专题：离线算法
ID
Problem
Score
专题：比较复杂的题目
ID
Problem
Score
ID
Problem
Score
ID
Problem
Score
ID
Problem
Score
Activity
刷题进度
加载中...
0
已完成
0
总题数
0
待完成
Less More
All Topics
滑动窗口与双指针
103 Problems
二分算法
130 Problems
单调栈
50 Problems
网格图
70 Problems
位运算
113 Problems
图论算法
170 Problems
动态规划
669 Problems
常用数据结构
533 Problems
数学算法
0 Problems
贪心与思维
0 Problems
链表、二叉树与回溯
0 Problems
字符串
0 Problems