大家好，我是 方圆。最近仓库 Star 星数增长蛮快的，实在感谢大家。这个仓库是我在算法学习路上总结的经验性知识，目前来说我认为其中缺憾的地方是动态规划和图没有专题文章，如果后续有时间，我会尽快整理出来。算法学习在我看来是一件需要占用大块时间去做的事情，对于我现在的工作状态来说，比较难拿出十天半个月来做这件事情了，所以也希望大家能够提 Pull Request 共同建设。
我重新将题目的顺序整理了一下，我认为比较合适的顺序是：双指针、滑动窗口和二分查找，接下来是数据结构链表、栈、队列、散列表等等，换个脑子学习一下排序算法，接下来就是树、图数据结构，再就是回溯、动态规划等等，最后是树状数组和线段树，我觉得这两部分内容作为扩展学习更合适。另外我也整理了 掘金 和 CSDN 的专栏，大家按照喜好看自己喜欢的网站吧，方便的话，可以在掘金上帮忙点个关注（我总觉得 CSDN 是一个没有人在运营的博客网站...），希望大家算法学习的开心~
- 算法学习指南: https://juejin.cn/post/7339042929883381795
- 掘金专栏地址：https://juejin.cn/column/7409850315203985427
- CSDN 专栏地址：https://blog.csdn.net/qq_46225886/category_10010696.html
- 相关学习：关于双指针算法问题的思考
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 125. 验证回文串 简单 | Solution125.java | ✅Character.isLetterOrDigit() 静态方法判断是字母和数字 |
| 面试题 17.11. 单词距离 中等 | Interview1711.java | ✅ |
| 809. 情感丰富的文字 中等 | Solution809.java | ✅ |
| 443. 压缩字符串 中等 | Solution443.java | ✅ |
| 481. 神奇字符串 中等 | Solution481.java | ✅ |
| 524. 通过删除字母匹配到字典里最长单词 中等 | Solution524.java | ✅ |
| 777. 在LR字符串中交换相邻字符 中等 | Solution777.java | |
| 838. 推多米诺 中等 | Solution838.java | ✅ |
| 面试题 01.05. 一次编辑 中等 | Interview0105.java |
- 相关学习：滑动窗口算法技巧
- 相关学习：二分查找是偏爱细节的魔鬼
查找峰值是非常典型的根据数据二段性进行二分的题目
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 162. 寻找峰值 中等 | Solution162.java | ⭐️ |
| 852. 山脉数组的峰顶索引 中等 | Solution852.java |
前缀和表示数组的前 n 项和，它是一种数据预处理的方法，是对空间换时间的应用，我们一般会创建 数组长度 + 1 大小的数组来记录前缀和，并将 0 索引处的前缀和标记为 0，表示前 0 项和，如下图所示，索引 1 处的前缀和表示原数组中的前 1 项和（nums[0]），所以我们想获取原数组中某索引元素的前缀和的话，需要将索引值加 1 再从前缀和数组中取值。
一般 连续子数组 求和且不涉及区间修改的问题都可以使用前缀和来求解，通过 前缀和减法计算 我们能计算出任意区间和，这一点很重要，利用这一点可以解决很多区间求和的问题。
- 一维数组前缀和计算模板如下：
int[] preSum = new int[nums.length + 1];
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}我们能通过前缀和减法计算任意区间和，即 preSum[k, i] = preSum[0, i] - preSum[0, k - 1]，其中 k <= i
我觉得 304 题是二维数组前缀和的代表性题目，熟悉它的解题思路之后，大概几分钟就能解出来。我们以计算 matrix[i][j] 处的前缀和为例，其中二维数组中每个元素表示以 [0, 0] 为左上角，以当前元素 [i, j] 为右下角构成的矩阵的前缀和，在计算 matrix[i][j] 之前，我们先来看一下官方题解给出示例图，我觉得记住这张图能的推导出计算公式：
计算 matrix[i][j] 我们能够依靠已知的前缀和 matrix[i - 1][j - 1]、matrix[i - 1][j] 和 matrix[i][j - 1]，其实我们可以轻易的根据图示得出 matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1]，为什么要减去 matrix[i - 1][j - 1] 呢，因为在 matrix[i - 1][j] 和 matrix[i][j - 1] 中都包含着 matrix[i - 1][j - 1]，我们做加和计算时把 matrix[i - 1][j - 1] 加了两遍，所以需要再减去一个，记住这个图示之后遇到类似的题推导一下就可以了，不必记住模板。
计算二维数组前缀和的要点一定是确定好 矩形的对角（左上角和右下角 或 左下角和右上角）
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 中等 | NumMatrix.java | |
| 661. 图片平滑器 简单 | Solution661.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 14. 最长公共前缀 简单 | Solution14.java | |
| 1455. 检查单词是否为句中其他单词的前缀 简单 | Solution1455.java | startsWith() 方法 |
| 187. 重复的DNA序列 中等 | Solution187.java | |
| 面试题 10.02. 变位词组 中等 | Interview1002.java | |
| 394. 字符串解码 中等 | Solution394.java | |
| 151. 反转字符串中的单词 中等 | Solution151.java | |
| 165. 比较版本号 中等 | Solution165.java | Integer.parseInt() 字符串转整数自动忽略前导0 |
| 8. 字符串转换整数 (atoi) 中等 | Solution8.java | ⭐️数字边界问题处理 |
| 43. 字符串相乘 中等 | Solution43.java | |
| 6. Z 字形变换 中等 | Solution6.java |
链表是一种 递归 的数据结构，与数组不同的是它不需要占用连续的内存空间，但是需要额外的空间保存后继节点的指针，以此将所有的链表节点串联起来。它的删除和插入操作比较高效，时间复杂度为
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while (head != null) {
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}| 题目链接 | 题解 | 备注 |
|---|---|---|
| 206. 反转链表 简单 | Solution206.java | |
| 234. 回文链表 简单 | Solution234.java | 快慢指针分开链表 |
| 92. 反转链表 II 中等 | Solution92.java | |
| 25. K 个一组翻转链表 困难 | Solution25.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 剑指 Offer 22. 链表中倒数第k个节点 简单 | SolutionOffer22.java | |
| 876. 链表的中间结点 简单 | Solution876.java | |
| 141. 环形链表 简单 | Solution141.java | |
| 142. 环形链表 II 中等 | Solution142.java | |
| 287. 寻找重复数 中等 | Solution287.java | ⭐️ 1. 如果提示 n + 1 个数，且数字范围在 [1, n] 内，那么可以使索引和该位置的值一致，来协助解题2. 该题由于不能修改数组，所以转换成了环形链表求解 |
| 160. 相交链表 简单 | Solution160.java | |
| 1823. 找出游戏的获胜者 中等 | Solution1823.java |
栈是一种基于 后进先出（LIFO）策略 的集合类型，这就需要我们在对值进行处理时注意结果值有没有对顺序的要求，因为入栈到出栈是倒序的。
- 应用: 函数调用栈、括号的匹配、双栈实现浏览器的前进和后退功能、JVM栈、电子邮件的存放、算数表达式的求值(操作数栈和运算符栈)
- 相关学习：单调栈和单调队列可以很简单
单调栈本质上是 维护数组中的元素为单调序列，数组中的元素 要么 符合单调性顺利进栈，要么 不符合单调性而将栈中其他元素“挤走”再进栈，使得栈中序列始终满足单调性。
理解这一点很重要，我们以单调递增栈为例，如果出现了比栈顶元素 小 的值，即不符合当前栈中序列单增特性的值，那么它会使所有比它大的值出栈，而 该值便是接下来要连续出栈元素右侧最近的小值，比该值大的值出栈完毕后，该值进栈，使得栈中的序列仍然满足单调递增。
如果题目有 在连续序列中找元素左/右侧最近的大/小值 的特点，我们就可以使用单调栈来求解，找最近的小值的单调递增栈模板如下，注意入栈的是数组元素的索引而不是元素值：
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
int index = stack.pop();
// 关于 index 的特殊处理
process();
}
// 索引入栈
stack.push(i);
// 处理逻辑
process1();
}这个模板其实很好记，根据想找小值还是找大值来确定模板中的 while 条件，如果找小值则使用小于号，则 nums[i] < nums[stack.peek()]，如果找大值则使用大于号，则 nums[i] > nums[stack.peek()]，再根据题意判断是否需要给大于小于号添加上等号，这一点考虑是在有重复值出现的情况下。
说了这么多，其实只需要考虑想找的是最近的小值还是大值，写对应的模板解题即可，即使你没明白为什么单调栈能找元素最近的大/小值（应该自己 Debug 学习一下）也没关系，只要使用了单调栈它就有这个性质，其他的全是虚妄......
该类型题目不直接要求找某元素左/右侧最近的大/小值，而是利用单调栈能找到某元素最近的大值/小值的特点来 确定当前元素作为区间内最大值/最小值时的区间范围（这么说起来有点儿绕），以此来计算该元素对题解的"贡献"。
我们初始化每个元素的默认区间范围如下，这是该元素作为极值时的特殊情况：
int[] left = new int[nums.length];
Arrays.fill(left, -1);
int[] right = new int[nums.length];
Arrays.fill(right, nums.length);以当前元素作为区间内最大值为例，记录每个元素能到达的左侧/右侧的最远距离：
Stack<Integer> stack = new Stack<>();
// 正序遍历计算上界
for(int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
right[stack.pop()] = i;
}
stack.push(i);
}
stack.clear();
// 逆序遍历计算下界
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
left[stack.pop()] = i;
}
stack.push(i);
}注意，记录的区间范围为全开区间，所以如果在计算区间长度时需要减 1，而且当题目中没有规定所有值都不同时，有时需要为其中一个（正序或逆序）遍历条件增加等号，避免发生“重复统计”。
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 795. 区间子数组个数 中等 | Solution795.java | 乘法原理和重复值判断很需要注意 |
| 907. 子数组的最小值之和 中等 | Solution907.java | |
| 84. 柱状图中最大的矩形 困难 | Solution84.java | ⭐️ |
| 85. 最大矩形 困难 | Solution85.java | 转换成 84 题来求解 |
先进先出队列（简称队列）是一种基于先进先出（FIFO）策略的集合类型，它相比于栈多了能够在队首操作的方法，所以使用栈能解决的问题队列也能解决，不过使用队列解决的问题会突出 需要操作两端数据 的特点。
单调队列是在单调栈的基础上实现了对 序列的两端操作，所以使用单调队能让我们 获取区间最值（队首即为最值）和 移除队首值。此外 不要局限 在只使用一个单调队列解题，有的题目需要维护两个单调队列来分别记录区间内的最大值和最小值来求解。
理论上使用单调栈能解决的问题单调队列也能解决，不过在我们不需要获取区间最值时还是使用单调栈来求解。
能获取区间最大值（nums[deque.peekFirst()]）的单调递减队列模板如下：
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
int index = deque.pollLast();
// 关于 index 的特殊处理
process();
}
deque.addLast(i);
// 必要处理逻辑
process1();
}- 相关学习：一文搞懂优先队列及相关算法
实现散列表分为两步：
- 用散列函数将被查找的键转化为数组的一个索引，理想情况下，不同的键都能转化为不同的索引值
- 处理碰撞冲突，有两种常见的处理方法，分别为拉链法和线性探测法。前者的方法是将发生碰撞的元素保存在链表中；后者的思想是与其将内存用作链表，不如将它们保存在散列表的空元素中
散列表数据结构使用了适度的空间和时间，并在这两个极端之间找到了平衡
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 插入排序 | InsertSort.java | |
| 希尔排序 | ShellSort.java | |
| 选择排序 | SelectionSort.java | |
| 冒泡排序 | BubbleSort.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 归并排序：基本实现 | MergeSort.java | |
| 归并排序：将多次创建小数组的开销转换为只创建一次大数组 | MergeSort2.java | |
| 归并排序：当数组有序时，跳过 merge() 方法 | MergeSort3.java | |
| 归并排序：对小规模子数组使用插入排序 | MergeSort4.java | |
| 快速排序：基本实现 | QuickSort.java | |
| 快速排序：基准数优化 | QuickSort2.java | |
| 快速排序：切换到插入排序 | QuickSort3.java | |
| 快速排序：三向切分 | QuickSort4.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 桶排序 | BucketSort.java | |
| 计数排序 | CountingSort.java | |
| 基数排序 | RadixSort.java |
- 相关学习：树专题 —— 二叉搜索树和中序遍历
- 相关学习：树专题 —— 二叉树前序遍历
- 相关学习：树专题 —— 二叉树后序遍历
- 相关学习：树专题 —— 二叉树层序遍历
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 左倾红黑树 | LeftLeaningRedBlackTree.java | 树专题 —— 深入理解左倾红黑树 |
| 经典红黑树 | / | 树专题 —— 深入理解经典红黑树 |
| 2034. 股票价格波动 中等 | StockPrice.java | |
| 220. 存在重复元素 III 困难 | Solution220.java | 滑动窗口 + 红黑树 |
深度优先搜索是先寻找离起点更远的顶点，只有在碰到死胡同时才访问近处的顶点；广度优先搜索则会先覆盖起点附近的顶点，只有在临近的所有顶点都被访问了之后才能前进。
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 无向图 | Graph.java | |
| 深度优先搜索 | DepthFirstPaths.java | |
| 广度优先搜索 | BreadthFirstPaths.java | |
| Prim算法查找最小生成树 | PrimMST.java | |
| 有向图 | Digraph.java | |
| Dijkstra算法查找最短路径 | Dijkstra.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 207. 课程表 中等 | Solution207.java | 判断是否有环 |
拓扑排序是一种对有向无环图中顶点进行排序的算法，在拓扑排序中，如果图中存在一条从顶点 A 到顶点 B 的路径，那么在排序中顶点 A 出现在顶点 B 的前面，需要应用拓扑排序求解的题目会给出“顶点”间存在依赖关系的条件。
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 创建有向图
Digraph digraph = new Digraph(numCourses, prerequisites);
// 拓扑排序求解
return digraph.topological();
}
static class Digraph {
// 顶点数
private final int V;
// 邻接表
private final HashSet<Integer>[] adj;
// 入度
private final int[] inDegree;
public Digraph(int numCourses, int[][] prerequisites) {
this.V = numCourses;
inDegree = new int[V];
adj = new HashSet[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new HashSet<>();
}
// 初始化邻接表并统计每个顶点的入度
for (int[] prerequisite : prerequisites) {
adj[prerequisite[1]].add(prerequisite[0]);
inDegree[prerequisite[0]]++;
}
}
/**
* 拓扑排序：找到图中入度为 0 的顶点，以及由入度为 0 顶点所指向的顶点
*/
public int[] topological() {
// 将所有入度为 0 的顶点入队
ArrayDeque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
deque.offer(i);
}
}
// 将队列执行出队操作，出队的顺序就是拓扑序
int index = 0;
int[] res = new int[V];
while (!deque.isEmpty()) {
Integer v = deque.poll();
for (Integer w : adj[v]) {
inDegree[w]--;
// 入度为 0 入队
if (inDegree[w] == 0) {
deque.offer(w);
}
}
res[index++] = v;
}
if (index == res.length) {
return res;
}
return new int[0];
}
}| 题目链接 | 题解 | 备注 |
|---|---|---|
| 210. 课程表 II 中等 | Solution210.java | |
| 802. 找到最终的安全状态 中等 | Solution802.java | |
| 851. 喧闹和富有 中等 | Solution851.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 1519. 子树中标签相同的节点数 中等 | Solution1519.java |
- 相关学习：深入理解回溯算法
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 257. 二叉树的所有路径 简单 | Solution257.java | |
| 78. 子集 中等 | Solution78.java | |
| 17. 电话号码的字母组合 中等 | Solution17.java | |
| 131. 分割回文串 中等 | Solution131.java | |
| 784. 字母大小写全排列 中等 | Solution784.java | |
| 22. 括号生成 中等 | Solution22.java | ⭐️ |
| 139. 单词拆分 中等 | Solution139.java | 字符串API word.startsWith(s); 和备忘录 |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 77. 组合 中等 | Solution77.java | |
| 39. 组合总和 中等 | Solution39.java | |
| 40. 组合总和 II 中等 | Solution40.java | ⭐️ |
| 216. 组合总和 III 中等 | Solution216.java |
| 题目链接 · | 题解 | 备注 |
|---|---|---|
| 46. 全排列 中等 | Solution46.java | |
| 47. 全排列 II 中等 | Solution47.java | ⭐️ |
| LCR 157. 套餐内商品的排列顺序 中等 | SolutionLCR157.java | |
| 面试题 08.12. 八皇后 困难 | Interview0812.java | |
| 10. 正则表达式匹配 困难 | Solution10.java |
动态规划（dynamic programming）常用于 解决最优问题，它与分治法相似，都是通过组合子问题的解来求解原问题（programming 在这指的是一种表格法，而非计算机编程）。分治法是将问题分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。相反地，动态规划应用于子问题重叠的情况，即不同的子问题具有公共子问题，如果采用分治法的话，会反复地求解公共子问题，而动态规划算法对每个子问题只求解一次，并将解保存在表格中（也就是常用的dp数组），以便下次需要同样的子问题求解时，避免重复计算。
当发现题目需要采用动态规划求解时，一般需要考虑如下问题：
- 这个问题的 base case 是什么？base case 是一些简单的，能直接列出来的子问题的解，求解其他父问题时，需要依赖这些 base case
- 考虑如何利用这些 base case 求解父问题（也是网上常说归纳状态转移方程）
- 考虑如何定义dp来记录这些解，一般情况下一维dp数组就足够，像路径问题和子序列问题考虑使用二维dp数组
注意求解两字符串相比较的问题时（如编辑距离问题），一般定义二维dp数组，如下图所示，dp数组定义的长度和宽度分别为两字符串长度加一，黄色的方格为初始化 base case，记蓝色方格为待求解方格，其对角线方向的红色方格表示的是相等字符串的值。可以通过红色、绿色和紫色方格对蓝色方格进行求解：
- 红色 -> 蓝色：表示已经相等的字符串经操作后再相等的结果值
- 绿色 -> 蓝色：表示字符串text1转换成字符串text2的结果值
- 紫色 -> 蓝色：表示字符串text2转换成字符串text1的结果值
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 377. 组合总和 Ⅳ 中等 | Solution377.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 198. 打家劫舍 中等 | Solution198.java | |
| 740. 删除并获得点数 中等 | Solution740.java | |
| 2320. 统计放置房子的方式数 中等 | Solution2320.java | |
| 213. 打家劫舍 II 中等 | Solution213.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 53. 最大子数组和 中等 | Solution53.java | |
| 2606. 找到最大开销的子字符串 中等 | Solution2606.java | |
| 1749. 任意子数组和的绝对值的最大值 中等 | Solution1749.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 322. 零钱兑换 中等 | Solution322.java | |
| 343. 整数拆分 中等 | Solution343.java | |
| 264. 丑数 II 中等 | Solution264.java | |
| 面试题 17.09. 第 k 个数 中等 | Interview1709.java | |
| 1218. 最长定差子序列 中等 | Solution1218.java |
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 64. 最小路径和 中等 | Solution64.java | |
| LCR 166. 珠宝的最高价值 中等 | SolutionLCR166.java | |
| 72. 编辑距离 中等 | Solution72.java |
涉及子序列，一般情况下时间复杂度为
- 针对数组的最长递增子序列问题：
int n = array.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = 最值;
}
}- 针对两个数组或字符串的子序列问题：
int n1 = array1.length;
int n2 = array2.length;
int[][] dp = new int[n1][n2];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (n1[i] == n2[j]) {
dp[i][j] =
} else {
dp[i][j] =
}
}
}| 题目链接 | 题解 | 备注 |
|---|---|---|
| LCR 185. 统计结果概率 中等 | SolutionLCR185.java | |
| 467. 环绕字符串中唯一的子字符串 中等 | Solution467.java |
递归矩阵问题注意单元格重复访问的问题，一般用 visited[][] 来标记是否访问过
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 200. 岛屿数量 中等 | Solution200.java | |
| LCR 129. 字母迷宫 中等 | SolutionLCR129.java | |
| LCR 130. 衣橱整理 中等 | SolutionLCR130.java | |
| 79. 单词搜索 中等 | Solution79.java |
贪心算法可以通过局部最优解来构造全局最优解，也就是说，在构造局部最优解时只需关注当前问题，而不必考虑子问题的解。这也是贪心算法与动态规划不同的地方，动态规划需要在每个步骤中都要进行一次选择，通常以一种自底向上的方式求解（先求子问题，再求较大的子问题），而贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题变得更小，它可能依赖之前做出的选择，但不依赖任何将来的选择或是子问题的解。
相关学习：深入理解树状数组
树状数组是一种简单的数据结构，它支持单点修改和区间查询操作，一般的 RMQ 问题优先选择树状数组求解，而不是线段树，后者相对来说代码量大，也比较复杂
- 树状数组解题模板：BinaryIndexedTree.java
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 307. 区域和检索 - 数组可修改 中等 | NumArray.java | |
| 1395. 统计作战单位数 中等 | Solution1395.java | ⭐️ |
| 2179. 统计数组中好三元组数目 困难 | Solution2179.java | |
| 775. 全局倒置与局部倒置 中等 | Solution775.java | |
| 327. 区间和的个数 困难 | Solution327.java |
相关学习：深入理解线段树
线段树可以解决区间和、区间最大值或区间最小值的问题（RMQ 问题），不过线段树的代码量相对来说较大而且比较复杂，所以线段树是在前缀和、差分和树状数组解决方法之后不得已才会考虑的方案。 一般使用线段树的题目都具备 区间修改和区间查询 的特点，如果大家在这里是按照顺序刷的话，应该对 RMQ 问题有一个比较充分的了解了，在这里做一下相关题型解法的归纳：
- 数组不变，区间查询：前缀和、树状数组和线段树
- 数组单点修改，区间查询：树状数组和线段树
- 数组区间修改，单点查询：差分和线段树
- 数组区间修改，区间查询：线段树
注意每种题型涉及的解法都是越靠前越优先考虑。
- 线段树模板：SegmentTree.java
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 307. 区域和检索 - 数组可修改 中等 | NumArray.java | |
| 239. 滑动窗口最大值 困难 | Solution239.java | |
| 654. 最大二叉树 中等 | Solution654.java |
- 线段树模板：SegmentTree2.java
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 1893. 检查是否区域内所有整数都被覆盖 简单 | Solution1893.java | |
| 1109. 航班预订统计 中等 | Solution1109.java |
- 线段树模版：SegmentTree3.java
| 题目链接 | 题解 | 备注 |
|---|---|---|
| 729. 我的日程安排表 I 中等 | MyCalendar.java | |
| 731. 我的日程安排表 II 中等 | MyCalendarTwo.java | ⭐️ |
| 732. 我的日程安排表 III 困难 | MyCalendarThree.java | |
| 715. Range 模块 困难 | RangeModule.java | ✅️ 理解 add 是作为区间变化量还是区间内单个值的变化量 |