欢迎来到我的小站\o/欢迎来到我的小站。

ST表(Sparse Table)，是解决可重复贡献问题的区间查询的数据结构，可以做到时间复杂度O(NlogN)的预处理和O(1)的查询。 可重复贡献问题：对于运算opt满足x opt x == x（例如max(x, x…

最近公共祖先(LCA，Lowest Common Ancestor (LCA))，是经典的树上问题。因为在树上两个点之前有且仅有一条路径联通，因此求出两个节点的LCA，知道了路径的拐点之后，就可以解决很多树上的路径问题。…

树状数组（Fenwick Tree, Binary Indexed Trees, BIT）是一种能够快速修改并查询数组前缀和的数据结构。 从树状数组的英文名 Binary Indexed Trees 或许更好理解，树状数…

数论分块，是一种能在O(sqrt(n))复杂度下枚举x / i的值的算法 满足式子n / i == n / j的j的最大值为n / (n / i) 也就是说下面这两段代码等价： #include <bits/stdc++…

背包DP分为01背包、完全背包、多重背包等等 背包容量有限，在 n 个物品中拿若干个，如何使得拿到的物品价值最大 因为一个物品只有拿或者不拿两种选择，因此称为01背包 状态定义：dp[i][j]表示在只考虑前i个物品的情…

动态规划（Dynamic Programming, DP），动态规划是一种重要的思维方法，通过利用已有的子问题信息高效求出当前问题的最优解。使用动态规划需要满足三个条件：最优子结构，无后效性和子问题重叠。 最优子结构：一…