当前位置：首页 > article >正文

算法技巧及模板总结

article 2024/12/1 14:28:37

文章目录

算法技巧及模板总结
- 二分
- - 二分查找
  - 二分答案
- 滑动窗口
- - 定长滑动窗口
  - 不定长滑动窗口
- dfs和bfs
- - dfs求连通块节点个数
  - 求最短路
  - - 朴素Dijkstra---适用于稠密图
    - 堆优化Dijkstra---适用于稀疏图
    - Floyd求最短路
    - 01bfs
    - 判断稀疏图和稠密图
    - Dijkstra和Floyd的比较
- 回溯
- - 子集型
  - 组合型
  - 排列型
- 乘法逆元
- 快速幂
- 时间类的问题
- 判断平方数
- 字符串api
- 数位之和两种写法---循环、字符串
- 求素数的三种方法(式除法、埃式筛、线性筛或称欧拉筛)
- 记忆化搜索和动态规划
- - 记忆化搜索翻译成动态规划注意事项(步骤)
  - 如何理解记忆化搜索转化成dp的遍历顺序？
  - 选或不选和枚举选哪个的抉择
  - 背包问题
  - - 01背包
    - 完全背包
    - 背包模板及各种问题的转化
  - 线性dp
  - - 最长公共子序列(LCS)
    - 最长递增子序列(LIS)
    - 最大子数组和
  - 状态机dp
  - 区间dp
  - 树型dp
  - - 树的直径
  - 状态压缩DP
- 最大子数组和
- 二进制枚举
- 枚举因子
- 数位之和两种写法---循环、字符串
- 位运算
- - lowbit模板---取出x最低位的1和0
  - **将n转化成二进制和的形式存在数组中**
  - 快速求x * 2^i
  - 求x里有多少个1的api
- gcd和lcm
- 单调栈
- 并查集
- 树状数组
- - 单点修改、区间查询
  - 区间修改、单点查询---当成差分用
  - 适用于力扣的线段树类
- 线段树
- 最小质因数预处理
- 分解质因数
- 最近公共祖先lca
- 前后缀分解
- 拓扑排序
- 组合数模板
- 判断二分图
- 二维前缀和
- 反悔贪心
- 思考问题的启发
- - 求子序列长度问题---可以转化成子串长度问题
  - 正难则反
  - 遇事不决先排序
  - 贡献法
  - 绝对差
  - 子数组计数
- 常见错误总结
- - move函数的使用
  - 差分数组
  - 自定义排序方式
  - 前后缀分解如何确定数组长度
  - 累和出现的错误
  - unordered_map和map

算法技巧及模板总结

二分

二分查找

以34.在排序数组中查找元素的第一个和最后一个位置经典题目为例，这的lower_bound()函数是用来求第一个大于等于target的下标，这一个函数其实能解决大部分问题，主要有大于等于、大于、小于、小于等于，但是都能够通过这一个函数转化过来

左闭右闭

//左闭右闭写法 [l, r]
int lower_bound1(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    //区间没有元素的状态是l>r 那么上一个状态(l<=r)就是循环条件
    while(l <= r) {
        int mid = l+(r-l)/2;
        if(nums[mid] < target) l = mid+1;
        else r = mid-1;
    }
    return l;
}

左闭右开

//左闭右开写法 [l, r)
int lower_bound2(vector<int>& nums, int target) {
    int l = 0, r = nums.size();
    //区间没有元素的状态是l==r 那么上一个状态(l<r)就是循环条件
    while(l < r) {
        int mid = l+(r-l)/2;
        if(nums[mid] < target) l = mid+1;
        else r = mid;   //哪边是开区间，那边就不需要1
    }
    return l;   //return r也行
}

左开右开

//左开右开写法 (l, r)
int lower_bound3(vector<int>& nums, int target) {
    int l = -1, r = nums.size();
    //区间没有元素的状态是l+1==r 那么上一个状态(l+1<r)就是循环条件
    while(l+1 < r) {
        int mid = l+(r-l)/2;
		if(nums[mid] >= target) r = mid;
        else l = mid;
    }
    return r
}

//左开右开写法 (l, r)
int lower_bound3(vector<int>& nums, int target) {
    int l = -1, r = nums.size();
    //区间没有元素的状态是l+1==r 那么上一个状态(l+1<r)就是循环条件
    while(l+1 < r) {
        int mid = l+(r-l)/2;
        if(nums[mid] < target) l = mid;
        else r = mid;   //哪边是开区间，那边就不需要1
    }
    return l+1; //return r也行
}

通过这几种写法的特点，我总结了几个规律：

1、确定区间，三种区间的表达方式
2、循环条件的判断：先想好区间没有元素的状态那么上一个状态就为循环条件，只改运算符即可
3、防止溢出mid = l+(r-l)/2
4、哪边是开区间哪边就不能加一
5、第一个if语句干脆全都写成if(nums[mid] < target) l = ...省略号处更具区间开闭情况来判断是否加一
6、最后返回的下标，看循环不变量

二分答案

二分答案分为两种，求最小和求最大，这有点联想到高中的知识了，求最小我们就需要找大于等于的式子，求最大就需要找小于等于的式子。

求最小

今天刷了二分答案求最小，算是打开新世界的大门了，有多了一个求最小的方法了，刷到的这几个题都感觉有一个特点，应该也可以算得上是单调性吧，然后就是一定要会写check函数，然后呢check函数的返回值与二分的答案的正关系或者负关系要理清，这对应在二分的时候对边界的修改是不同的，所以我觉得要判断这一点很重要，其次就是二分答案的初始化一定要写对，今天也在这里栽了跟头。

求最大

大致和求最小相反，找到的规律和如何记忆放在下面了

区分求最大、最小

当已经分析到能够用二分答案的写法来解决这一题的时候需要思考一下步骤：先看答案求的是最大还是最小，这样可以先判断出是二分最小的方法还是二分最大的方法，其次找到题干中的另外一个限定条件，这通常就是check函数的结果，只有check函数写对了，边界才能正确的移动，边界如何移动就需要判断是求最大还是最小

以开区间为例：
求最小：check(mid) == true ===> r = mid，最后返回r
求最大：check(mid) == true ===> l = mid，最后返回l
什么情况才是true呢？这就要从题目中找了，通常在给定的另一个参数的限定，比如875给了一个参数int h，题干中最后问：返回她可以在 h 小时内吃掉所有香蕉的最小速度 k ，这里的限定就是<=h，那么二分答案的时候check里计算sum的时候如果最后的sum<=h那么就为true
怎么确定左右边界的初始值？----得先看是求最小还是求最大，以求最小为例，最后返回的是r，所以就以r为视角去找能够取的最大和最小值，注意那么右边界其实可以无限大，只需要左边界是r取得的最小值-1即可。
同理求最大就以l为视角，右边界就为l能取的最大值+1

滑动窗口

定长滑动窗口

这种一般题干中会给出滑动窗口的长度k，然后让你求出所有这些长度的滑动窗口中的最大、最小、子数组数目。最大或者最小可能是平均值、和、距离值等等，一般这种定长滑动窗口相对简单，如果想出来的是一个n^2的复杂度的方法肯定是不能ac这一题的，滑动窗口的复杂度是O(n)的，总结的模板大致分为三个步骤：入、维护答案、出。通常滑动窗口类型的题目需要借助哈希表来达到元素相同个数，元素不同个数这种条件。

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        long long ans = 0, sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            cnt[nums[i]]++;	//入
            if(i < k-1) continue;	//没有达到窗口大小直接跳过后面的步骤
            if(cnt.size() == k) ans = max(ans, sum);	//维护答案
            int out = nums[i-k+1];
            sum -= out;
            if(--cnt[out] == 0) cnt.erase(out);	//出
        }
        return ans;
    }
};

不定长滑动窗口

这种类型的考法就相对来说比较多了，主要分为三类：求最长子数组，求最短子数组，以及求子数组个数，然后经过这一次的周赛(9.29)，求子数组个数又可以细分成：越长越合法(ans+=l)、越短越合法(ans+=r-l+1)、恰好型滑动窗口。对于恰好型滑动窗口就可以把问题转化成两个至多或者两个至少的问题，如果转化成两个至少的问题，那么恰好k就可以表示成 f(k) - f(k + 1) ，如果转化成两个至多的问题，那么恰好k就可以表示成f(k)-f(k-1)

dfs和bfs

力扣平台有时候给你的就是一个邻接表，这意味着它直接帮你初始化邻接表了就只需要管如何搜索就行了，但是对于其它的平台就都需要自己初始化邻接表，下面是初始化邻接表的代码示范：
表示x点和y点有边的邻接表

无权：

vector<vector<int>> adj(n);	//这个n一定不能忘
for (auto &edge : edges) {
    int x = edge[0], y = edge[1];
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
}

有权：

vector<vector<pair<int, int>>> adj(n+1);
for(auto& r : roads) {
    adj[r[0]].push_back({r[1], r[2]});
    adj[r[1]].push_back({r[0], r[2]});
}

邻接矩阵初始化：

vector<vector<int>> adj(n, vector<int>(n, INT_MAX/2));
//邻接矩阵初始化
for(auto& t : times) {
    adj[t[0]-1][t[1]-1] = t[2];
}

邻接矩阵adj[i] [j]表示i到j有一条权值为t[2]的有向边

除此之外，有时候也可以初始化一个二维矩阵，比如g[i] [j] = 1表示点i和j有关系，这样的情况就不需要像上面的操作了，就直接搜索这个二维矩阵就行了

dfs求连通块节点个数

vector<bool> visited(n, false);
function<int(int)> dfs = [&](int i) -> int{
    int sz = 1;
    visited[i] = true;
    for(int& a : adj[i]) {
        if(!visited[a]) sz += dfs(a);
    }
    return sz;
};

求最短路

朴素Dijkstra—适用于稠密图

以743.网络延迟事件为例

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> adj(n, vector<int>(n, INT_MAX/2));
        //邻接矩阵初始化
        for(auto& t : times) {
            adj[t[0]-1][t[1]-1] = t[2];
        }
        vector<int> dis(n, INT_MAX/2), vis(n, false);
        dis[k-1] = 0;   //从下标k-1为起点
        while(true) {
            int x = -1;
            for(int i = 0; i < n; i++) {
                //先找未被访问的点 再从未访问的点中找距离最小的点下标
                if(!vis[i] && (x < 0 || dis[i] < dis[x])) x = i;
            }

            //都已经访问过了 直接返回最大值 都访问过了 不可能出现INT_MAX/2
            if(x < 0) return ranges::max(dis);

            //没有边到未访问的点x
            if(dis[x] == INT_MAX/2) return -1;

            vis[x] = true;	//表示已访问
            
            //挨个求其临界点的最短路径
            for(int y = 0; y < n; y++) {
                dis[y] = min(dis[y], dis[x]+adj[x][y]);
            }
        }
    }
};

堆优化Dijkstra—适用于稀疏图

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> adj(n);
        //这里用邻接表了 不再是邻接矩阵了
        for(auto& t : times) adj[t[0]-1].emplace_back(t[1]-1, t[2]);
        vector<int> dis(n, INT_MAX);
        dis[k-1] = 0;	//根据题意 从哪开始就是dis[...]=0
        //堆的定义一定要正确 <dis[k], k>
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, k-1);
        while(!pq.empty()) {
            auto [dx, x] = pq.top();
            pq.pop();

            //之前出堆过 因为第二次出堆的dis一定比第一次出堆的dis大
            if(dx > dis[x]) continue;

            //更新最短路径
            for(auto& [y, d] : adj[x]) {
                int new_dis = dx+d;
                if(new_dis < dis[y]) {
                    dis[y] = new_dis;   //更新x的邻居的最短路
                    pq.emplace(new_dis, y);
                }
            }
        }
        int mx = ranges::max(dis);
        return mx < INT_MAX ? mx : -1;
    }
};

Floyd求最短路

以1334.阈值距离内邻居最少的城市

记忆化搜索：

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        //创建邻接矩阵
        vector<vector<int>> adj(n, vector<int>(n, INT_MAX/2));
        for(auto& e : edges) {
            adj[e[0]][e[1]] = e[2];
            adj[e[1]][e[0]] = e[2];
        }

        // 记忆化搜索
        vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n, -1)));
        auto dfs = [&](auto&& dfs, int k, int i, int j) -> int {
            if(k < 0) return adj[i][j];
            int& res = memo[i][j][k];
            if(res != -1) return res;
            return res = min(dfs(dfs, k-1, i, j), dfs(dfs, k-1, i, k)+dfs(dfs, k-1, k, j));
        };

        int ans = 0, mn = n;
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                //记忆化搜索
                if(j != i && dfs(dfs, n-1, i, j) <= distanceThreshold) cnt++;
            }
            if(cnt <= mn) {
                mn = cnt;
                ans = i;
            }
        }
        return ans;
    }
};

递推：

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        //创建邻接矩阵
        vector<vector<int>> adj(n, vector<int>(n, INT_MAX/2));
        for(auto& e : edges) {
            adj[e[0]][e[1]] = e[2];
            adj[e[1]][e[0]] = e[2];
        }

        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n, vector<int>(n, 0)));
        dp[0] = adj;
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    dp[k+1][i][j] = min(dp[k][i][j], dp[k][i][k]+dp[k][k][j]);
                }
            }
        }

        int ans = 0, mn = n;
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                //递推
                if(j != i && dp[n][i][j] <= distanceThreshold) cnt++;
            }
            if(cnt <= mn) {
                mn = cnt;
                ans = i;
            }
        }
        return ans;
    }
};

Floyd主要是从dfs开始，而Dijkstra是类似于从queue开始，感觉Floyd更难理解一点。首先得理解灵神给出的递推关系式：
$df s (k, i, j) = min (df s (k - 1, i, j), df s (k - 1, i, k) + df s (k - 1, k, j))$
首先这个dfs(k, i, j)定义成表示从 i 到 j 的最短路长度，并且这条最短路的中间节点编号都 ≤k。注意中间节点不包含 i 和 j。不选k好理解，直接递归到上一个状态dfs(dfs, k-1, i, j)。主要是需要理解选的意思：选的话就分解成了从i到k-1和k-1到j的最短路问题了，这两个子问题的编号都不包含k，所以第一个参数都变成了k-1。最终递归退出的边界就是k<0的状态。

01bfs

这个是Dijkstra的简化版本，需要发现边权只为0和1的特点，这样就可以用01bfs来解决，利用deque双端队列代替最小堆来解决最短路的问题。

以3286.穿越网格图的安全路径为例

class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int m = grid.size(), n = grid[0].size();
        int dirs[][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        dis[0][0] = grid[0][0];
        deque<pair<int, int>> dq;
        dq.emplace_front(0, 0);
        while(!dq.empty()) {
            auto [x, y] = dq.front();
            dq.pop_front();
            for(auto& dir : dirs) {
                int dx = x+dir[0], dy = y+dir[1];
                if(dx >= 0 && dx < m && dy >= 0 && dy < n) {
                    int new_dis = dis[x][y]+grid[dx][dy];
                    if(new_dis < dis[dx][dy]) {
                        dis[dx][dy] = new_dis;
                        //为0入队首 为1入队尾
                        grid[dx][dy] == 0 ? dq.emplace_front(dx, dy) : dq.emplace_back(dx, dy);
                    }
                }
            }
        }
        return dis[m-1][n-1] < health;

    }
};

整体步骤和bfs很像，只不过是多了一个dis数组来维护最短路径，在这一题中如果最短路径(对应这里的最小消耗)是小于health的表明是能都到达最右下角的

判断稀疏图和稠密图

点的个数的平方远大于边的个数，那么这个就是稀疏图，如果点的个数的平方接近边的个数，那么这个就是一个稠密图。

Dijkstra和Floyd的比较

个人觉得Floyd更适合用在稠密图上，看了几个用Floyd解的题目，它们都是用邻接矩阵初始化的，时间复杂度是n^3，是基于记忆化搜索和递推的一个求最短路问题，当查询比较多的时候通常就用Floyd

Dijkstra是求单源最短路径的方法，是基于队列(01bfs用双端队列，堆优化用堆)实现的求最短路的方法，这里面通常需要定义一个dis数组。时间复杂度是log级别的，添加边比较多的时候通常用Dijkstra。

回溯

通常有两种思路，分别是选或不选和选哪个的思维，感觉都不是很好理解。目前也判断不出来什么题型一定用哪一个更好，目前只能是试错阶段了，做题的时候那就两种方法都思考一下吧

子集型

一定要搞清楚子集的概念吧，拿78题为例，有三个元素的数组，那么它的子集个数就为2的3次幂个，下面给出两种实现方法，选或不选和枚举选哪个

选或不选：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        int n = nums.size();

        auto dfs = [&](auto&& dfs, int i) -> void {
            if(i == n) {
                ans.push_back(path);
                return;
            }

            //不选
            dfs(dfs, i+1);

            //选
            path.push_back(nums[i]);
            dfs(dfs, i+1);
            path.pop_back();
        };

        dfs(dfs, 0);
        return ans;
    }
};

枚举选哪个：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;

        int n = nums.size();
        auto dfs = [&](auto&& dfs, int i) -> void {
            ans.push_back(path);

            for(int j = i; j < n; j++) {
                path.push_back(nums[j]);
                dfs(dfs, j+1);
                path.pop_back();
            }
        };

        dfs(dfs, 0);

        return ans;
    }
};

组合型

这个类型的题目还是和子集型有点像的，就是在子集的基础上添加了path的长度限定，比如77.组合这一题，path的长度就限定为了2，而且，通常从后往前遍历比较好，这样对于还能否选(剪枝)比较好思考些。后面遇到的记忆化搜索也通常是从后往前去想递推

枚举选哪个：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](auto&& dfs, int i) -> void {
            int d = k-path.size();
            if(d == 0) {
                ans.push_back(path);
                return;
            }

            for(int j = i; j >= d; j--) {
                path.push_back(j);
                dfs(dfs, j-1);
                path.pop_back();
            }
        };

        dfs(dfs, n);

        return ans;
    }
};

选或不选：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](auto&& dfs, int i) -> void {
            int d = k-path.size();
            if(d == 0) {
                ans.push_back(path);
                return;
            }

            //可以不选
            if(i > d) dfs(dfs, i-1);

            //选
            path.push_back(i);
            dfs(dfs, i-1);
            path.pop_back();
        };

        dfs(dfs, n);

        return ans;
    }
};

排列型

对于这种类型的回溯通常用枚举选哪个更好，因为全排列每一次都是要从头到尾dfs一遍，当然在这过程中需要配合上哈希表来记录已经访问过的元素。这里再熟悉一遍排列的定义吧：n的排列意思是长度为n，并且每个元素1到n只出现一次的集合，以46.全排列为例

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        int n = nums.size();
        vector<bool> onPath(n, false);

        auto dfs = [&](auto&& dfs, int i) -> void {
            if(i == n) {
                ans.emplace_back(path);
                return;
            }

            for(int j = 0; j < n; j++) {
                if(!onPath[j]) {
                    onPath[j] = true;
                    path.emplace_back(nums[j]);
                    dfs(dfs, i+1);
                    path.pop_back();
                    onPath[j] = false;
                }
            }
        };

        dfs(dfs, 0);

        return ans;
    }
};

乘法逆元

这里就直接把灵神的结论搬过来吧~

MOD = 1_000_000_007

// 加
(a + b) % MOD

// 减
(a - b + MOD) % MOD

// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD

// 乘（注意使用 64 位整数）
a * b % MOD

// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD

// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * qpow(b, MOD - 2, MOD) % MOD

乘法和加法都是很常见的，最需要注意的就是减法和除法，乘法逆元就是来解决这个除法的问题的。该方法是用快速幂(qpow)来计算逆元的。通过这样，我感觉可以重新写一遍快速幂的板子了。

快速幂

#define int long long
const int mod=1e9+7;
int qpow(int a, int n, int mod) {
    int res = 1;
    while(n) {
        if(n&1) res = (res*a)%mod;
        a = a*a%mod;
        n >>= 1;
    }
    return res;
}

学习了逆元求法之后总结了一个既适合求逆元的又适合普遍求快速幂的一段通用代码了，如果是求逆元，分子是什么qpow的第一个参数就是什么，第二个参数根据题意是以什么取模就填mod-2。总之第三个参数就是根据题意中的mod设置是多少就是多少

时间类的问题

这种题最开始遇到的时候感觉很麻烦，一般会给出形如hh:mm:ss这种的字符串，给出一种思考的方向，也就是可以尝试先将所有都转化成秒的形式，可以用一个lambda表达式写一个函数来实现。有时还会遇到这样一种情况，就是要输出hh:mm:ss。

转化成秒

auto trans = [&]() {
    string s;
    cin >> s;
    return stoi(s.substr(0, 2))*3600+stoi(s.substr(3, 2))*60+stoi(s.substr(6, 2));
};

输出hh:mm:ss

printf("%02lld:%02lld:%02lld\n", h, m, s);

之所以用lld是因为h，m，s都是long long类型的，这个的作用就是保证hms输出都是两位数，如果是一位数就有前导0补充

判断平方数

int tmp = sqrt(num);
if(num == tmp*tmp) cout << "是平方数";
else cout << "不是平方数";

字符串api

slower(char c) 是否为小写字母
isupper(char c) 是否为大写字母
isdigit(char c) 是否为数字
isalpha(char c) 是否为字母
isalnum(char c) 是否为字母或者数字
toupper(char c) 字母小转大
tolower(char c) 字母大转小
substr(i, len)字符串截取，从下标i开始，截取len个字符
s.find("abc") != s.npos表示在字符串s中找到了字符串"abc"

数位之和两种写法—循环、字符串

//写法一：
int target = 3487568927346, ans = 0;
for(int t = target; t > 0; t /= 10) ans += target%10;

//写法二：
int target = 3487568927346, ans = 0;
string s = to_string(target);
for(char c : s) ans += c-'0';

求素数的三种方法(式除法、埃式筛、线性筛或称欧拉筛)

也是接受了之前一直很难理解的东西了，果然以前弄不懂的最终还是会给自己一个暴击！这个求素数的题出现在牛客练习赛129上。
试除筛

void solve() {
    int n;
    cin >> n;
    auto isprime = [&](int x) {
        for(int i = 2; i*i <= x; i++) {
            if(x%i == 0) return false;
        }
        return x >= 2;
    };
    //输出n以内的素数
    for(int i = 2; i <= n; i++) {
        if(isprime(i)) cout << i << " ";
    }
}

这里有一点点的优化就是i*i <= x，这是通过性质来判断的，如果i是x的一个因子，那么x/i也会是x的一个因子，这两个因子又分居在根号n的左右两端，所以循环条件在i*i <= x即可

埃式筛

const int N = 1000;
vector<int> isPrime(N+1, true);
vector<int> primes{0};  //防止二分查找下标溢出

int init = []() -> int {
    for(int i = 2; i <= N; i++) {
        if(isPrime[i]) {
            primes.push_back(i);
            for(int j = i; j <= N/i; j++) {
                isPrime[i*j] = false;
            }
        }
    }
    return 0;
}();

先判断是否为素数，如果为素数那么再进行将后面的合数筛选掉

线性筛（欧拉筛）

const int N = 1000;
vector<int> isPrime(N+1, true);
vector<int> primes{0};  //防止二分查找下标溢出

int init = []() -> int {
    for(int i = 2; i <= N; i++) {
        if(isPrime[i]) primes.push_back(i);
        for(int j = 1; j < primes.size() && i*primes[j] <= N; j++) {
            isPrime[i*primes[j]] = false;
            if(i%primes[j] == 0) break;
        }
    }
    return 0;
}();

不同于埃式筛，这里是从最小质因数开始筛，因为埃式筛会有很多重复筛的地方，比如12和18，他们先后会被2和3筛，所以会有重复的地方，用线性筛就只会被2筛掉

记忆化搜索和动态规划

记忆化搜索翻译成动态规划注意事项(步骤)

以70.爬楼梯为例。首先要确保记忆化搜索跑出来的代码是正确且不超时的，然后第一点先关注的应该是递归的边界if(i<=1)那么i为1的时候就退出递归了，那么最后一个状态是i=2，这个时候再看递推关系式res = dfs(dfs, i-1)+dfs(dfs, i-2);我们发现i-2最小也是0，是不会对数组越界的，所以不需要改变递推关系式，如果会越界，就根据情况改变递推式，可以参考打家劫舍那一题。对于如果修改递推关系式的话，跟nums数组没关系，之和你的dp数组有关系，举个例子打家劫舍中dfs(dfs, i) = max(dfs(dfs, i-1), dfs(dfs, i-2)+nums[i]);改变递推式后为dfs(dfs, i+2) = max(dfs(dfs, i+1), dfs(dfs, i)+nums[i]);。再然后就是将递推变成循环，我觉得容易出现问题的地方在初始值和边界值上。初始值的话，可以看记忆化搜索的递归边界前的第一个状态，而结束边界的话我觉得要根据题意来判断，比如数组边界之类的吧。剪枝操作一定要在边界返回的条件之前！

如何理解记忆化搜索转化成dp的遍历顺序？

这一点主要看递推式是什么样的，假如递推式形如dp[i][j] = dp[i+1][j]...的式子，我们可以观察到这个i是由后一个状态而来，所以我们遍历i的时候应该从后往前遍历，而对于j的话就没有什么特定的要求，它正向或者逆向遍历都是可以的

选或不选和枚举选哪个的抉择

从当前这个数是否影响相邻几个数来思考：

不考虑相邻元素，也就是选了nums[i]后i+1,i…的元素都不能选—>选或不选—2140.解决智力问题
考虑相邻元素，也就是选了nums[i]后i+1,i…的元素还是能选—>枚举选哪个—2944.购买水果最少金币数

当然也会有两种方法都适用的情况

背包问题

01背包

所有物品只能选一次，弄清楚什么是容量，什么是背包。01背包的问题通常分为三种：

最多放…物品，求最大价值
恰好放…物品，求方案数，递归返回的答案为c==0
至少放…物品，求最小价值

以494为例，这一题是求方案数的，大致模板如下

auto dfs = [&](auto&& dfs, int i, int c) -> int {
    if(i < 0) return c == 0;    //如果c==0表示是一个合法的方案返回1，否则不是合法方案返回0
    int& res = memo[i][c];
    if(res != -1) return res;
    if(c < nums[i]) return res = dfs(dfs, i-1, c);
    return res = dfs(dfs, i-1, c) + dfs(dfs, i-1, c-nums[i]);
};

对于01背包的递推式通常为：res = max(dfs(dfs, i-1, c) , dfs(dfs, i-1, c-nums[i])+val[i]);，如果是求最小就将max换成min，求方案数就把max、val[i]去掉然后把逗号改成加法就行。至于为什么是改成加法呢？灵神给出了很好的解答：这叫加法原理，如果事件 A 和事件 B 是互斥的（即不能同时发生，不选 nums[i] 的同时，又选了 nums[i]），那么发生事件 A 或事件 B 的总数等于事件 A 的数量加上事件 B 的数量。

完全背包

完全背包是01背包的无约束版本，可以不用选完所有物品，任何物品可以选任意次，主要的不同就是在递推关系式上，选的话上一个状态也是i，下面是322.零钱兑换的示例代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> memo(n, vector<int>(amount+1, -1));
        auto dfs = [&](auto&& dfs, int i, int c) -> int {
            if(i < 0) {
                //如果没有恰好装下那么返回一个很大的int 以便后面取min
                return c == 0 ? 0 : INT_MAX/2;  
            }

            int& res = memo[i][c];
            if(res != -1) return res;
            if(c < coins[i]) return res = dfs(dfs, i-1, c);
            return res = min(dfs(dfs, i-1, c), dfs(dfs, i, c-coins[i])+1);
        };

        int ans = dfs(dfs, n-1, amount);

        return ans < INT_MAX/2 ? ans : -1;
    }
};

背包模板及各种问题的转化

vector<vector<int>> memo(n, vector<int>(m+1, -1));//数组大小因题而异 不能死板硬套
auto dfs = [&](auto&& dfs, int i int j) -> int {
    if(i < 0) return 0;	//如果是求方案数	要写成return c == 0
    int& res = memo[i][j];
    if(res != -1) return res;
    if(c < nums[i]) return res = dfs(dfs, i-1, j);	//容量小于当前物品重量搜索前一个状态
    //如果是求方案数 逗号变成加号，val[i]去掉，max去掉 
    //如果是完全背包 第二个状态是dfs(dfs, i, j-nums[i]) 因为完全背包可以重复选
    return res = max(dfs(dfs, i-1, j), dfs(dfs, i-1, j-nums[i])+val[i]);
};

变化细节都在注释里头了

线性dp

最长公共子序列(LCS)

通常有两种状态：1、s1[i] == s2[j]2、s1[i] != s2[j]，它们的状态来源于左、上、左上，但是在两种情况下某些状态是不必要的。下面给出1143.最长公共子序列的ac代码：

记忆化搜索：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> memo(n, vector<int>(m, -1));
        auto dfs = [&](auto&& dfs, int i, int j) -> int {
            //有一个子序列遍历到头就结束
            //边界状态也好理解 s1="",s2="abc"它们最长公共子序列长度为0，所以这里返回0
            if(i < 0 || j < 0) return 0; 
            int& res = memo[i][j];
            if(res != -1) return res;
            //相等情况下 不需要考虑dfs(i-1, j)和dfs(i, j-1)
            if(text1[i] == text2[j]) return res = dfs(dfs, i-1, j-1)+1;
            //不相等情况下 不需要考虑dfs(i-1, j-1)
            return res = max(dfs(dfs, i-1, j), dfs(dfs, i, j-1));
        };
        return dfs(dfs, n-1, m-1);
    }
};

dp：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(text1[i] == text2[j]) dp[i+1][j+1] = dp[i][j]+1;
                else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
        return dp[n][m];
    }
};

最长递增子序列(LIS)

大概发现了一种思路，像这种子序列问题+数据范围比较小的题目一般都是用记忆化搜索/dp来做，因为dp本质上来说就是一种暴力，只不过是一种递推的形式，递推关系式难写而已。这个就是想清楚了子问题就比较好想明白这个递推关系式了，dp[i]的最长递增子序列就是在i之前的最长递增子序列的情况下加上1，当然在这前提必须是if(nums[j] < nums[i])，下面是两种写法的样例：

记忆化搜索：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n);    //这一题memo只能初始化成0，最后return ++res表明对res进行了修改
        auto dfs = [&](auto&& dfs, int i) -> int {
            //if(i < 0) return 0; //这里的i不可能出现0 可以省略掉
            int& res = memo[i];
            if(res > 0) return res;
            for(int j = i-1; j >= 0 ;j--) {
                if(nums[j] < nums[i]) res = max(res, dfs(dfs, j));
            }
            return ++res;
        };
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans = max(ans, dfs(dfs, i));
        }
        return ans;
    }
};

dp：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n+1);
        for(int i = 0; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j]);
            }
            dp[i]++;
        }
        return ranges::max(dp);
    }
};

最大子数组和

这种题也可以用前缀和+枚举右维护左来解决，要用dp的话，就要将dp[i]定义成nums[i]及以前的最大子数组和，然后状态定义方程就变成了：

dp[0] = nums[0];
for(int i = 1; i < nums.size(); i++) dp[i] = max(dp[i-1], 0) + nums[i];

状态机dp

典型是买卖股票类型的题目，一般定义dp[i] [j]表示已nums[i]为结尾状态[j]的最优解。给出122.示例代码

记忆化搜索：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<array<int, 2>> memo(n, {-1, -1});   //memo[i][0]---未持股  memo[i][1]---持股
        auto dfs = [&](auto&& dfs, int i, bool hold) -> int {
            if(i < 0) return hold ? INT_MIN : 0;    //不可能还没遍历数组就出现持股状态
            int& res = memo[i][hold];
            if(res != -1) return res;
            if(hold) return res = max(dfs(dfs, i-1, true), dfs(dfs, i-1, false)-prices[i]);
            return res = max(dfs(dfs, i-1, false), dfs(dfs, i-1, true)+prices[i]);
        };
        return dfs(dfs, n-1, 0);
    }
};

dp：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        vector<array<int, 2>> dp(n+1);
        dp[0][1] = INT_MIN;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 2; j++) {
                if(j) dp[i+1][j] = max(dp[i][1], dp[i][0]-prices[i]);
                else dp[i+1][j] = max(dp[i][0], dp[i][1]+prices[i]);
            }
        }
        return dp[n][0];
    }
};

其实递归的入口准确来说应该是max(dfs(n-1, 0), dfs(n-1, 1))，但是如果最后一天还持有股票的话利润一定比未持有股票的利润少，所以就没有必要写dfs(n-1, 1)

区间dp

这个dp的特点是：通常是在一个区间序列上进行操作，例如对一个数组的子区间进行合并、计算最优值等操作。问题的解通常与区间的划分和组合有关。

树型dp

树的直径

这种题型也算是困扰我许久的了，在牛客上遇到的比较多，经常看到题解写的树上dfs，来历应该就是在这里了，原来灵神归到了树型dp上了，这里也介绍了dfs(int x, int fa)的由来，以及为什么要有个int fa这个参数。这里拿2246.相邻字符不同的最长路径举例，为什么这一题可以算是树的直径类型题目呢？虽然看上去是求符合条件的点的个数，其实也就是符合条件的边的个数+1。示例代码如下：

有向树写法：

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = s.size();
        vector<vector<int>> g(n);

        //建图 表示parent[i]能够到达i 从1开始遍历因为i=0已经是根节点，没有其它点指向它
        for(int i = 1; i < n; i++) g[parent[i]].push_back(i);

        int ans = 0;
        auto dfs = [&](auto&& dfs, int x) -> int {
            int maxLen = 0;
            for(auto y : g[x]) {
                int len = dfs(dfs, y)+1;
                
                //确保相邻不相等
                if(s[y] != s[x]) {
                    ans = max(ans, maxLen+len);	//在遍历的过程中维护最大值
                    maxLen = max(maxLen, len);
                }
            }
            return maxLen;
        };
        dfs(dfs, 0);
        return ans+1;
    }
};

无向树写法：

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = s.size();
        vector<vector<int>> g(n);

        //建图 表示parent[i]能够到达i 从1开始遍历因为i=0已经是根节点，没有其它点指向它
        for(int i = 1; i < n; i++) {
            g[parent[i]].push_back(i);
            g[i].push_back(parent[i]);
        }

        int ans = 0;
        auto dfs = [&](auto&& dfs, int x, int fa) -> int {
            int maxLen = 0;
            for(auto y : g[x]) {
                if(y == fa) continue;
                int len = dfs(dfs, y, x)+1;
                
                //确保相邻不相等
                if(s[y] != s[x]) {
                    ans = max(ans, maxLen+len);
                    maxLen = max(maxLen, len);
                }
            }
            return maxLen;  //为空或者相邻相等都返回0
        };
        dfs(dfs, 0, -1);
        return ans+1;
    }
};

在无向图的写法中，就遇到了这个在牛客中经常遇到的fa这个dfs参数，我的理解是这个图先是建的无向图，然后在遍历的时候如果当前节点和fa相同的话其实是重复遍历的，或者说其实是不能到达的，所以需要这一步。这一题写完题解也是才明白能和这个字符串s构建起联系了，就是在判断是否相邻用到了一下，这个s其实感觉有点类似于hash的作用了

状态压缩DP

我的理解是二进制枚举+DP，由于状态个数可能很多，或者说因为状态数量而导致的超时或超内存，在考虑到能用二进制压缩的时候就变成了状态压缩DP了，能用二进制来压缩的话就使得了状态转移方程缩小了一个维度。然后就是判断能否用状态压缩：考虑状态的时候仅仅只有两个方面，比如说选或不选、true或false，这种只有两面性的东西就可以用状态压缩来做。目前仅仅只达到了理解的程度~

最大子数组和

Kadane 算法：dp[i] = max(dp[i-1], 0)+nums[i]

二进制枚举

来源于atcoder374的一次讲解，当发现枚举的时候只存在两种方向的时候可以联想到二进制，达到二进制枚举的效果，这样代码会变得很简洁！题目来源于ABC374的C题，这里也贴一下实现的代码。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto& ai : a) cin >> ai;
    int ans = INT_MAX;
    //所有可能的情况2^n次方-1
    for(int s = 0; s < (1<<n); s++) {
        int ga = 0, gb = 0;
        //1---加入到b组 0---加入到a组
        for(int i = 0; i < n; i++) {
            if((s>>i)&1) gb += a[i];
            else ga += a[i];
        }
        ans = min(ans, max(ga, gb));
    }
    cout << ans << "\n";
}

枚举因子

第一次遇到来源于于力扣3164.优质数对的总数II，感觉很陌生，记下来

unordered_map<int, int> cnt;
for(int d = 1; d*d <= n1; d++) {
    if(n1%d) continue;  //n1不是d的倍数直接跳过
    cnt[d]++;
    if(d*d < n1) cnt[n1/d]++;   //不能写d*d<=n1，以9为例，如果写的小于等于那么3会记录两次
}

整个过程是枚举n1的所有因子并保存到cnt哈希表中，主要优化的点在于这是个根号n的一个复杂度。

数位之和两种写法—循环、字符串

//写法一：
int target = 3487568927346, ans = 0;
for(int t = target; t > 0; t /= 10) ans += target%10;

//写法二：
int target = 3487568927346, ans = 0;
string s = to_string(target);
for(char c : s) ans += c-'0';

位运算

lowbit模板—取出x最低位的1和0

//取出最低位1
int lowbit = x&-x;	

//取出最低位0
int t = ~x;	//先对x取反
int lowbit = t&-t;

将n转化成二进制和的形式存在数组中

vector<int> power;
int lowbit;
while(n) {
    lowbit = n&(-n);//-n也就是n^1
    power.push_back(lowbit);
    n ^= lowbit;//减去最低位
    //n -= lowbit;
}

快速求x * 2^i

求2的i次幂可以用左移来解决，当然右移就相当于除法

void solve() {
    cout << (5<<3) << "\n";	//求5 * 2^3
    cout << (40>>3) << "\n";	//求40/2^3
}

求x里有多少个1的api

int cnt = __builtin_popcount(x);

gcd和lcm

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

a * b = gcd(a, b)*lcm(a, b)
int lcm(int a, int b) {
    return a/gcd(a, b)*b;
}

void solve() {
    cout << gcd(15, 10) << "\n";	//5
    cout << lcm(15, 10) << "\n";	//30
}

单调栈

大致模板，以739.日常温度为例

从右往左、栈中记录下一个更大(或小)的元素

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st;	//下一个更大的元素
        for(int i = n-1; i >= 0; i--) {
            while(!st.empty() && temperatures[st.top()] <= temperatures[i]) st.pop();
            if(!st.empty()) ans[i] = st.top()-i;
            st.push(i);
        }
        return ans;
    }
};

从左往右、栈中记录还没算出下一个更大(或更小)元素的下标

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st;  //还未找到下一个更大元素的下标
        for(int i = 0; i < n; i++) {
            int t = temperatures[i];
            while(!st.empty() && t > temperatures[st.top()]) {
                int j = st.top();
                st.pop();
                ans[j] = i-j;
            }
            st.push(i);
        }
        return ans;
    }
};

首先得判断出我要找当前位置后面的小于还是大于这个值的第一个数，可以想象成一行高楼，从左往右看，高的楼会挡住后面低的楼，所以这是一个找下一个大于当前高度的值。一般也就只有两种类型，假设当前值为nums[i]：1、找第一个大于nums[i]的值；2、找第一个小于nums[i]的值

并查集

大致模板：

vector<int> fa(n+1);
iota(fa.begin(), fa.end(), 0);
auto find = [&](auto&& find, int x) -> int {
    return x == fa[x] ? fa[x] : fa[x] = find(find, fa[x]);
};
auto merge = [&](int u, int v) -> void {
    int fx = find(find, u), fy = find(find, v);
    if(fx != fy) fa[fx] = fa[fy];
};

理解：大致讲述的是连通块和连通块之间的关系，单个连通块通过根来确定，通常要以某个方式为基准(最小下标或最大下标之类的)

树状数组

树状数组是什么？它是用来解决多次查询的前缀和数据结构，除此之外，在这期间还能对前缀和进行修改操作，这样是不是时间复杂度就大了很多？所以这里就用到了树状数组的一个数据结构来高效的维护对数组修改后的前缀和查询。树状数组的由来是线段树，看了俩小时没看懂线段树，它好像是递归+二分的思维，但是代码量实在有点多看不下去了。。。

单点修改、区间查询

int nums[500005], tree[500005];
int n, m;	//数组大小 查询长度

//添加操作 不断向上维护tree
void add(int idx, int val) {
    while(idx <= n) {
        tree[idx] += val;
        idx += idx&-idx;	//累加lowbit
    }
}

//求和操作 不断向下找区间和
int getSum(int idx) {
    int s = 0;
    while(idx > 0) {
        s += tree[idx];
        idx -= idx&-idx;	//累减lowbit
    }
    return s;
}

void solve() {
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> nums[i];
        add(i, nums[i]);
    }

    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a == 1) add(b, c);   //a是1的话执行add
        else cout << getSum(c)-getSum(b-1) << "\n"; //a是2的话执行求和
    }
}

唯一需要注意的点就在于这里的nums和tree数组的下标都是从1开始的，如果要在力扣中用到这个板子就需要注意一下下标的问题(idx都需要偏移)

区间修改、单点查询—当成差分用

int nums[500005], tree[500005];
int n, m;

void add(int idx, int val) {
    while(idx <= n) {
        tree[idx] += val;
        idx += idx&-idx;
    }
}

int getSum(int idx) {
    int s = 0;
    while(idx > 0) {
        s += tree[idx];
        idx -= idx&-idx;
    }
    return s;
}

void solve() {
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> nums[i];
    }

    while(m--) {
        int a, b, c, d;
        cin >> a;
        if(a == 1) {
            cin >> b >> c >> d;
            add(b, d);
            add(c+1, -d);
        } else {
            cin >> b;
            cout << nums[b]+getSum(b) << endl;
        }
    }
}

区间修改就相当于把这个树状数组当成了差分数组来做了

适用于力扣的线段树类

class FenwickTree {
    vector<int> tree;

public:
    binaryIndexTree(int n) : tree(n) {}

    void update(int i, int val) {
        for(; i < tree.size(); i += i&-i) {
            tree[i] += val;
        }
    }

    int pre(int i) {
        int s = 0;
        for(; i > 0; i -= i&-i) {
            s += tree[i];
        }
        return s;
    }

    int query(int l, int r) {
        if(r < l) return 0;
        return pre(r)-pre(l-1);
    }
};

//应用示例
int n = nums.size();
FenwickTree f(...);	//大小肯定是跟n相关，加一或减一、或不变 因题而异
f.update(...);
f.query(...);

需要注意的就是下标问题，力扣的数组都是从0开始的，所以在传参的时候注意下标别弄错就行

线段树

实现了区间修改和区间查询(洛谷3372)

const int N=500005;

#define lc p<<1
#define rc p<<1|1

int n, m, w[N];

struct node {
    int l, r, sum, add;  //左边界、右边界、区间和、懒标记
}tree[4*N];

//向上更新
void pushUp(int p) {
    tree[p].sum = tree[lc].sum+tree[rc].sum;
}

//向下更新
void pushDown(int p) {
    //当前节点没有懒标记就不需要向下更新
    if(tree[p].add) {
        tree[lc].sum += tree[p].add*(tree[lc].r-tree[lc].l+1);
        tree[rc].sum += tree[p].add*(tree[rc].r-tree[rc].l+1);
        tree[lc].add += tree[p].add;
        tree[rc].add += tree[p].add;
        tree[p].add = 0;    //父节点的懒标记向下更新完后要清零
    }
}

//二分递归地建树 三个参数分别为 根节点1 左边界 右边界
void build(int p, int l, int r) {
    tree[p] = {l, r, w[l]}; //只有在l == r时是最终值 其余都会在回溯的时候修改
    if(l == r) return;
    int m = l+r>>1;
    build(lc, l, m);
    build(rc, m+1, r);
    pushUp(p);
}

// //单点修改 参数分别为 根节点1 修改的位置 增加的值(注意是增加的值)
// void update(int p, int x, int k) {
//     //到达叶子节点
//     if(tree[p].l == tree[p].r) {
//         tree[p].sum += k;
//         return;
//     }
//     int m = tree[p].l+(tree[p].r-tree[p].l)/2;
//     if(x <= m) update(2*p, x, k);
//     else update(2*p+1, x, k);
//     tree[p].sum = tree[2*p].sum+tree[2*p+1].sum;    //回溯
// }

//区间查询 拆分与拼凑 覆盖就停止递归
int query(int p, int x, int y) {
    if(x <= tree[p].l && tree[p].r <= y) return tree[p].sum;
    int m = tree[p].l+tree[p].r>>1;
    pushDown(p);
    int sum = 0;
    if(x <= m) sum += query(lc, x, y);
    if(y > m) sum += query(rc, x, y);
    return sum;
}

//区间修改 参数：根节点 左边界 右边界 增加的值 有点类似于查询区间查询 覆盖了就停止递归
void lazyUpdate(int p, int x, int y, int k) {
    if(x <= tree[p].l && tree[p].r <= y) {
        tree[p].sum += (tree[p].r-tree[p].l+1)*k;   //改变的值是区间宽度*k
        tree[p].add += k;
        return;
    }
    int m = tree[p].l+tree[p].r>>1;
    pushDown(p);
    if(x <= m) lazyUpdate(lc, x, y, k);
    if(y > m) lazyUpdate(rc, x, y, k);
    pushUp(p);
}

主要思想是二分+分治+递归

最小质因数预处理

const int mx = 1e6;
int f[mx+1];

int init = []() -> int {
    for(int i = 2; i <= mx; i++) {
        if(f[i] == 0) {
            for(int j = i; j <= mx; j += i) {
                if(f[j] == 0) {
                    f[j] = i;
                }
            }
        }
    }
    return 0;
}();

有点类似于筛指数，有点像但不完全是！

分解质因数

void solve() {
    int x;
    cin >> x;
    set<int> st;
    for(int i = 2; i*i <= x; i++) {
        while(x%i == 0) {
            st.insert(i);
            x /= i;
        }
    }
    // 循环结束后，添加剩余的质因数  77末尾还要添加11
    if(x > 1) st.insert(x);
    for(auto& s : st) cout << s << " ";
}

主要是不能忘了最后一步添加剩余的质因数

最近公共祖先lca

const int N=5e5+10;

int n, m, s, a, b;
vector<vector<int>> e(N);
vector<int> dep(N);
vector<vector<int>> fa(N, vector<int>(20)); //fa[u][i]代表：起点u的前2^i层父亲节点

//点的下标从1开始 根节点的父亲是0，作为哨兵
void dfs(int u, int father) {
    dep[u] = dep[father]+1;

    //向上跳 1 2 4...
    fa[u][0] = father;
    for(int i = 1; i <= 19; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1]; //倍增递推式
    }

    for(int v : e[u]) {
        //无向树需要这步操作
        if(v != father) dfs(v, u);
    }
}

//查找u和v的最近公共祖先
int lca(int u, int v) {
    //保证u的深度大
    if(dep[u] < dep[v]) swap(u, v);

    //先跳到同一层
    for(int i = 19; i >= 0; i--) {
        if(dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    if(u == v) return v;    //同一层且跳到了相同节点直接返回
    //再一次lca 保证循环结束后u的第一个父节点就是公共节点
    for(int i = 19; i >= 0; i--) {
        if(fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void solve() {
    cin >> n >> m >> s;
    while(--n) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(4, 0);
    while(m--) {
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
}

不知道为啥这段代码在洛谷爆内存了，也没检查出是哪里错了，但是样例还是能跑的，应该整体代码不会错，主要是理解这个找祖先的思维：先dfs预处理dep和fa数组，是从上往下的；lca是从下往上的

前后缀分解

通常解决形如删掉其中某一个数，然后要求其它的和或者积之类的，总之相当于要枚举断点i，求i前面的什么东西和i后面的什么东西。写法有不同，但是大致意思都是一样的，都需要预处理pre和suf，只不过有的时候是和数组下标同步，有的时候会写成下标有偏移量，总之要弄明白意思。以238.除自身以外数组的乘积为例

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1), suf(n, 1), ans(n);
        for(int i = n-2; i >= 0; i--) suf[i] = suf[i+1]*nums[i+1];
        for(int i = 1; i < n; i++) pre[i] = pre[i-1]*nums[i-1];
        for(int i = 0; i < n; i++) ans[i] = pre[i]*suf[i];
        return ans;
    }
};

拓扑排序

这是图论中的应用，它有一个特点：只能先在队列中取出入度为0的点。以207.课程表为例，下面是给出广搜的大致模板

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int n = numCourses;
        vector<vector<int>> e(n);
        vector<int> din(n);
        queue<int> q;
        for(auto p : prerequisites) {
            e[p[1]].push_back(p[0]);
            din[p[0]]++;
        }
        for(int i = 0; i < n; i++) {
            if(din[i] == 0) q.push(i);
        }

        vector<int> vis;
        while(!q.empty()) {
            auto x = q.front();
            q.pop();
            vis.push_back(x);
            for(auto y : e[x]) {
                if(--din[y] == 0) {
                    q.push(y);
                }
            }
        }
        return vis.size() == n;
    }
};

队列q用来保存入度为0的点，din[i]表示i的度为多少，e为邻接表。创建邻接表的时候要注意一下，搞清楚是从哪个点出的，从哪个点入的。

组合数模板

const int MOD = 1'000'000'007;
const int MX = 2001;

long long q_pow(long long x, int n) {
    long long res = 1;
    for (; n > 0; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

// 组合数模板
long long fac[MX], inv_fac[MX];

auto init = [] {
    fac[0] = 1;
    for (int i = 1; i < MX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv_fac[MX - 1] = q_pow(fac[MX - 1], MOD - 2);
    for (int i = MX - 1; i > 0; i--) {
        inv_fac[i - 1] = inv_fac[i] * i % MOD;
    }
    return 0;
}();

long long comb(int n, int k) {
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

const mod = 1_000_000_007
const mx = 2000
var F, invF [mx + 1]int

func init() {
	F[0] = 1
	for i := 1; i <= mx; i++ {
		F[i] = F[i-1] * i % mod
	}
	invF[mx] = pow(F[mx], mod-2)
	for i := mx; i > 0; i-- {
		invF[i-1] = invF[i] * i % mod
	}
}

func pow(x, n int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n%2 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}

func comb(n, k int) int {
	return F[n] * invF[k] % mod * invF[n-k] % mod
}

判断二分图

特点

划分成两个集合，适合用染色法来理解

广搜写法(无向图)：

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(n+1);
        for(auto& d : dislikes) {
            g[d[0]].push_back(d[1]);
            g[d[1]].push_back(d[0]);
        }
        vector<int> color(n+1, -1);
        queue<int> q;
        for(int i = 1; i <= n; i++) {
            if(color[i] == -1) {
                q.push(i);
                color[i] = 0;
                while(!q.empty()) {
                    int x = q.front();
                    q.pop();
                    for(auto& y : g[x]) {
                        if(color[y] == -1) {
                            color[y] = 1^color[x];
                            q.push(y);
                        } else if(color[x] == color[y]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

还是觉得二分图的广搜好写一点，深搜逻辑不是很好懂，感觉有点剪枝的感觉，而且无向图和有向图的深搜写法还不同，所以还是就写上广搜的板子吧。

二维前缀和

int n, m;
cin >> n >> m;
vector<vector<int>> a(n+1, vector<int>(m+1));
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        char c;
        cin >> c;
        a[i][j] = c == '*';
    }
}
vector<vector<int>> pre(n+1, vector<int>(m+1));
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        pre[i][j] = pre[i-1][j]+pre[i][j-1]+a[i][j]-pre[i-1][j-1];
    }
}

需要画图来理解比较直观，然后就是数组a中"*“表示1，”."表示0，然后在数组a中是以下标1开头的，如果是力扣的题目要注意下标的偏移，当然前缀和数组的长度还是固定在n+1和m+1，就是在状态转移的时候要稍微注意一下，这个知识点最容易错的就是下标和状态转移方程

反悔贪心

是贪心算法的一种扩展，可以从字面上先理解：贪心地解决某个问题，但是在某个时刻发现当前的选择并不是最优选择，这时候可以反悔，通常用到的数据结构就是堆(优先队列)，首次了解是在双周赛144的T3.零数组变换III

思考问题的启发

求子序列长度问题—可以转化成子串长度问题

这有特定的场景要求，一般得先看看给出的数据是否有排序的限定，如果排序是不会改变答案的情况下那么求子序列长度的问题就可以通过排序转化成子串长度问题

正难则反

打一个比方，假如题干中要求的是…的最小次数、长度之类的，从反面思考就可以想成求出最长的符合条件的次数，然后用整体减去这个最长的一面，得到的答案就是这个最短的一面了

遇事不决先排序

当题中给出某些大小关系才能给出答案的字眼中，并且答案和顺序无关的时候可以先排序看看问题能不能变得简便很多

贡献法

这并没有模板，属于是思考问题的方向吧，通常在计数问题上有巧妙之处。就好比正常的计数逻辑，当数据范围扩大的时候正常的计数逻辑会超时，但是如果改变公式的顺序之类的话可能就会达到不一样的效果，通常叫做换个角度思考问题，灵神基本称之为横看成立侧成峰

绝对差

arr 中两个元素的间隔定义为它们下标之间的 绝对差 。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j| 。

这种问题的思考方向通常是前缀和，除此之外还有一种可能就是考虑相邻之间改变了什么，哪2121.相同元素的间隔之和举例，灵神的题解思路是考虑从p[i]到p[j]的时候绝对差改变的规律，它们改变的值是一个等式，式子为：sum = sum+i*(p[j]-p[i])-(n-i)*(p[j]-p[i])

子数组计数

通常要往以i下标为结尾的符合条件的子数组长度，最后的答案一般是ans += r-l+1或者ans += f[i]之类的结果，第一种情况比较符合滑动窗口，第二种就比较符合前缀和或者动态规划

常见错误总结

运算优先级：与运算要比或运算的优先级高

写函数的时候，或者传入数组的时候最好加上引用，今天也是遇到了一个因为没有为数组加上引用而导致爆内存的问题了，在调用函数的时候如果参数是数组，你不写引用的话那么会copy一份那个数组，所以这会耗费一定的空间。

move函数的使用

class Solution {
public:
    long long maxEnergyBoost(vector<int>& a, vector<int>& b) {
        int n = a.size();   //一定要在move函数之前
        vector<int> c[2] = {move(a), move(b)};
        vector<vector<long long>> memo(n, vector<long long>(2, -1));
        auto dfs = [&](auto&& dfs, int i, int j) -> long long {
            if(i < 0) return 0;
            long long& res = memo[i][j];
            if(res != -1) return res;
            return res = max(dfs(dfs, i-1, j), dfs(dfs, i-2, j^1))+c[j][i];
        };
        return max(dfs(dfs, n-1, 0), dfs(dfs, n-1, 1));
    }
};

这是一道状态机dp题，但是遇到的错误点在move函数的使用上，我自己写的时候int n = a.size()写在了move函数的下一行，结果导致程序怎么跑都输出0，问题就是在move函数上，调用move函数就相当于全部放到这个c二维数组中了，我试了一下如果要在move函数之后正确初始化n的话应该写成int n = c[0].size()

差分数组

注意能够定义差分数组的长度，如果到了1e9的长度就得用合并区间的写法了。差分数组长度的定义一定要准确，搞清楚右边界是多少，一定要确保不会越界，通常最保险的长度就是n+2

自定义排序方式

//以vector<pair<int, int>>为例
vector<pair<int, int>> t;
sort(t.begin(), t.end(), [](auto& a, auto& b) {
    //如果first不相等 按照first降序排列 
    //如果first相等 按照second升序排列
    if(a.first != b.first) {
        return a.first > b.first;
    }
    return a.second < b.second;
});
sort(t.begin(), t.end())

前后缀分解如何确定数组长度

在前后缀分解中确定数组长度，以及对应下标我觉得是最复杂的，如果想到了前后缀分解的解法很容易写出来，主要是下标对应和数组长度的初始化上我觉得是最让人头疼的。方法是看划分的范围：假设划分的范围是从[0, n-2]，所以前后缀数组最少就要定义成n，因为suf一般是suf[i+1]。然后就是搞清楚下标对应的含义，边界是包含还是不包含这很重要