2025-02-15[线段树]区间修改
线段树（区间修改）主要内容区间修改与懒标记 线段树是一种高效的数据结构，用于处理区间查询和修改操作。当涉及到区间修改时，懒标记（Lazy Propagation）是一种重要的优化手段，可以避免每次修改都直接更新所有节点，从而提高效率。懒标记的基本思想是将修改操作延迟到必要时才进行。 以下是懒标记的实现要点： 标记存储：在每个节点中存储懒标记，表示当前节点的区间需要进行的修改操作。 标记下推：在访
![2025-02-15[线段树]区间修改](https://pic--oss.oss-cn-beijing.aliyuncs.com/img/0f743f721cfcf20c3a1c3cf4a32f6fe.png)
2025-02-12[线段树]单点修改
线段树(单点修改)主要内容 注意：若只涉及到单点修改，则不需要pushdown（懒加载）操作。 例题最大数1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
2025-02-09最小生成树的扩展应用
最小生成树的扩展应用主要内容最小生成树相关知识点 定义与性质 最小生成树是指在一个加权连通图里，找到一棵生成树，其所有边的权值之和最小。 最小生成树的边数等于顶点数减1。 最小生成树不唯一，但其边权之和唯一。 Kruskal算法 基本思想：按照边权从小到大的顺序选择边，每次选择的边不会与已选择的边构成环，直到选择n-1条边为止。 实现步骤： 对所有边按照权值从小到大排序。 初始化并查集，每个顶
2025-02-06最小生成树的典型应用
最小生成树的典型应用主要内容1. 最小生成树的基本概念 定义：在一个加权连通图中，最小生成树是一个包含图中所有顶点的子图，且边的总权重最小。 应用场景：网络设计、城市规划、通信线路铺设等，目标是连接所有节点，同时最小化总成本。 一般思路： 2. 最小生成树的两种主要算法 Prim算法 适用场景：适用于稠密图（边数较多的图）。 时间复杂度：O(n2)，可以通过堆优化降低到 O(mlogn)。
2025-02-01单源最短路径的综合应用
单源最短路径的综合应用主要内容1. 单源最短路径问题概述单源最短路径问题是指在一个加权图中，找到从一个指定的源点到所有其他顶点的最短路径。常见的算法包括Dijkstra算法、Bellman-Ford算法和SPFA算法。选择合适的算法取决于图的特性和问题的具体需求。 2. 最短路径与其他知识点的结合应用在实际问题中，单源最短路径问题常常与其他知识点结合，形成更复杂的场景。以下是一些常见的结合应用：
2025-01-30单源最短路径建图方式
单源最短路径建图方式1. 主要内容1. SPFA算法模板代码123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;const int N = ..., M = ...; // 根据题目调整节点和边的数量int h[N]
2025-01-25区间合并
区间合并主要内容快速地将一系列区间中有交集（包括端点相交）的区间合并成一个,返回处理后的区间列表。 代码模板123456789101112131415161718void merge(vector<PII>& segs){ vector<PII> res; sort(segs.begin(),segs.end());//先按照左边界大小从小到
2025-01-25离散化
离散化主要内容 模板代码1234567891011121314vector<int> alls;//存储所有待离散化的值sort(alls.begin(),alls.end());//将所有值排序alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重//二分求出x对应的离散化下标int find(int x){