Typescript-Algorithms
    Preparing search index...

    数据结构题单 数据结构入门 数据结构新手教程 数据结构题目 力扣数据结构 leetcode数据结构 灵茶山艾府 灵神

    对于 双变量问题，例如两数之和 ai​+aj​=t，可以枚举右边的 aj​，转换成 单变量问题，也就是在 aj​ 左边查找是否有 ai​=t−aj​，这可以用哈希表维护。

    我把这个技巧叫做 枚举右，维护左。

    讲解

    下面这些题目，如果可以，请用一次遍历实现。

    思维扩展：

    对于三个或者四个变量的问题，枚举中间的变量往往更好算。

    为什么？比如问题有三个下标，需要满足 0≤i<j<k<n，对比一下：

    • 枚举 i，后续计算中还需要保证 j 和 k 的位置关系。
    • 枚举 j，那么 i 和 k 自动被 j 隔开，互相独立，后续计算中无需关心 i 和 k 的位置关系。

    所以枚举中间的变量更简单。

    讲解

    思维扩展：

    通常要用到「枚举右，维护左」的技巧。

    讲解

    前缀和与有序集合：

    思维扩展：

    图解

    推荐先阅读：从集合论到位运算，常见位运算技巧分类总结！

    思维扩展：

    【图解】一张图秒懂二维前缀和！

    二维前缀最小值：

    差分与前缀和的关系，类似导数与积分的关系。

    数组 a 的差分的前缀和就是数组 a。

    原理讲解

    【图解】从一维差分到二维差分

    注：部分题目可以不用栈，而是用一个数字记录嵌套深度。

    见 单调栈题单。

    队列常用在 BFS 中，见 网格图题单 和 图论题单。与此相比，栈常用在 DFS 中，但无需我们手动维护。

    个人觉得叫单调双端队列更准确。

    单调队列 = 滑动窗口 + 单调栈。

    问：入队、出队、更新答案，这三步的顺序如何思考？

    答：有两种情况。如果更新答案时，用到的数据包含当前元素，那么就需要先入队，再更新答案；如果用到的数据不包含当前元素，那么就需要先更新答案，再入队。至于出队，一般写在前面，每遍历到一个新的元素，就看看队首元素是否失效（不满足要求），失效则弹出队首。

    原理讲解

    关于单调队列优化 DP，见 动态规划题单 中的「§11.3 单调队列优化 DP」。

    部分题目也可以用二分解决。

    基于堆的反悔贪心。

    讲解

    部分题目需要结合懒删除堆。

    另见 图论题单 中的 Dijkstra 算法。

    模板

    思维扩展：

    部分题目也可以用试填法解决。

    模板：

    Python3

    Java

    C++

    Go

    class UnionFind:
    def __init__(self, n: int):
        # 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        # 集合 i 的代表元是自己，大小为 1
        self._fa = list(range(n))  # 代表元
        self._size = [1] * n  # 集合大小
        self.cc = n  # 连通块个数

    # 返回 x 所在集合的代表元
    # 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    def find(self, x: int) -> int:
        # 如果 fa[x] == x，则表示 x 是代表元
        if self._fa[x] != x:
            self._fa[x] = self.find(self._fa[x])  # fa 改成代表元
        return self._fa[x]

    # 判断 x 和 y 是否在同一个集合
    def is_same(self, x: int, y: int) -> bool:
        # 如果 x 的代表元和 y 的代表元相同，那么 x 和 y 就在同一个集合
        # 这就是代表元的作用：用来快速判断两个元素是否在同一个集合
        return self.find(x) == self.find(y)

    # 把 from 所在集合合并到 to 所在集合中
    # 返回是否合并成功
    def merge(self, from_: int, to: int) -> bool:
        x, y = self.find(from_), self.find(to)
        if x == y:  # from 和 to 在同一个集合，不做合并
            return False
        self._fa[x] = y  # 合并集合。修改后就可以认为 from 和 to 在同一个集合了
        self._size[y] += self._size[x]  # 更新集合大小（注意集合大小保存在代表元上）
        # 无需更新 _size[x]，因为我们不用 _size[x] 而是用 _size[find(x)] 获取集合大小，但 find(x) == y，我们不会再访问 _size[x]
        self.cc -= 1  # 成功合并，连通块个数减一
        return True

    # 返回 x 所在集合的大小
    def get_size(self, x: int) -> int:
        return self._size[self.find(x)]  # 集合大小保存在代表元上

    更多基础题，见 网格图题单 中的 DFS 和 图论题单 中的 DFS，其中大部分题目也可以用并查集实现。

    能用树状数组解决的题目，也能用线段树解决（反过来不一定）。但树状数组实现简单，代码短。

    为方便大家练习，我把适合用树状数组解决的题目分到树状数组中，其余分到线段树中。

    讲解：带你发明树状数组！附数学证明

    模板：

    Python3

    Java

    C++

    Go

    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:
        while i < len(self.tree):
            self.tree[i] += val
            i += i & -i

    # 计算前缀和 a[1] + ... + a[i]
    # 1 <= i <= n
    # 时间复杂度 O(log n)
    def pre(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.tree[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)

    除了可以用树状数组解决，部分题目也可以在归并排序的同时计算。

    线段树本质是二叉树，在学习之前，建议先做做 104. 二叉树的最大深度 和 111. 二叉树的最小深度（自底向上写法），当作热身。

    线段树：为什么要这样设计？ 理解线段树发明的动机。

    把任意区间用 O(logn) 个区间表示，线段树的每个节点记录对应区间的信息。

    • 询问：把询问区间拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点，把这 O(logn) 个节点的信息合并，即为答案。
    • 单点更新：有 O(logn) 个区间包含被修改的位置，需要更新 O(logn) 个节点的信息。

    基础模板代码如下。为方便入门理解，我没有做复杂封装。通用模板代码可以参考 AtCoder Library 的 segtree.hpp。

    Python3

    Java

    C++

    Go

    # 线段树有两个下标，一个是线段树节点的下标，另一个是线段树维护的区间的下标
# 节点的下标：从 1 开始，如果你想改成从 0 开始，需要把左右儿子下标分别改成 node*2+1 和 node*2+2
# 区间的下标：从 0 开始
class SegmentTree:
    def __init__(self, n: int, init_val=0):
        # 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 init_val
        # init_val 可以是 list 或者 int
        # 如果是 int，那么创建一个 list
        if isinstance(init_val, int):
            init_val = [init_val] * n
        self._n = n
        self._tree = [0] * (2 << (n - 1).bit_length())
        self._build(init_val, 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)

    思维扩展：

    把任意区间用 O(logn) 个区间表示，线段树的每个节点记录对应区间的信息。

    • 询问：把询问区间拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点，把这 O(logn) 个节点的信息合并，即为答案。
    • 区间更新：仍然是拆分成 O(logn) 个区间，对应着线段树的 O(logn) 个节点。但对于其中的非叶节点，不把更新的内容往下传递给子节点，而是记录「发生了更新，内容为 xxx」，把更新的内容记录下来。直到后续的询问或更新操作，需要访问或修改更下面的子节点信息时，才把更新的内容往下传。

    基础模板代码如下。为方便入门理解，我没有做复杂封装。通用模板代码可以参考 AtCoder Library 的 lazysegtree.hpp。

    Python3

    Java

    C++

    Go

    class Node:
    __slots__ = 'val', 'todo'

class LazySegmentTree:
    # 懒标记初始值
    _TODO_INIT = 0  # **根据题目修改**

    def __init__(self, n: int, init_val=0):
        # 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 init_val
        # init_val 可以是 list 或者 int
        # 如果是 int，那么创建一个 list
        if isinstance(init_val, int):
            init_val = [init_val] * n
        self._n = n
        self._tree = [Node() for _ in range(2 << (n - 1).bit_length())]
        self._build(init_val, 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)

    部分题目也可以用珂朵莉树解决。

    把询问排序，通过改变回答询问的顺序，使问题更容易处理。

    相应的，在线算法就是按照 queries 的顺序一个一个处理。

    如何科学刷题？

    1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
    2. 二分查找（二分答案/最小化最大值/最大化最小值/第K小）
    3. 单调栈（基础/矩形面积/贡献法/最小字典序）
    4. 网格图（DFS/BFS/综合应用）
    5. 位运算（基础/性质/拆位/试填/恒等式/思维）
    6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
    7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
    8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
    9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
    10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
    11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
    12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

    我的题解精选（已分类）

    欢迎关注 B站@灵茶山艾府

    如果你发现有题目可以补充进来，欢迎评论反馈。

    Settings

    Member Visibility

    On This Page

    零、常用枚举技巧一、前缀和二、差分三、栈四、队列五、堆（优先队列）六、字典树（trie）七、并查集八、树状数组和线段树九、伸展树（Splay 树）专题：离线算法关联题单算法题单