一个可以累死人的数据结构 线段树（仅限于基础的那个）（zx 树这种的以后再说） 线段树是一个神奇的数据结构，他基本上什么区间操作都可以优化 这里讲一些基本的操作：单点修改，区间查询，区间修改（延迟标记） 首先讲……概念…(我的线段树写的有的不一样，有的是用结构体存的左右节点，有的是在函数定义上存的节点) 线段树，顾名思义，一个树形结构，存储的每一个...

对前缀和与差分进行总结，来源：洛谷题单 首先 （由于之前教练和我说可以刷一刷洛谷的题单刷刷基础我就去了 正文 前缀和有几种，一维和二维的用的比较多。 一维前缀和比较简单，直接将数组的前几个加起来成一个单独的数组就可以 二维前缀和有点不一样：我们的二维前缀和处理的过程中不能直接通过上一个得到（需要三步操作其实也相当于直接得到。。。 在进行循环的时候，...

P1613 跑路 一道小绿题 虽然这只是一道小绿题但是我觉得还是有必要总结一下的因为不错 题目描述 你有辆很 n i u b i 的汽车一秒钟可以跑 2 的任意整次方的距离 给你一个有向图问：从 1 跑到 n 最短时间（边权都是 1） 先给一会思考一下 思路 首先，题目描述就让我们很容易想到倍增这个算法 我们需要把所有的边都存起来 但是一个问题是，...

Tree 洛谷 P2619 一道生成树的很好的题目 题目描述 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 need 条白色边的生成树。 乍一看还是很没有头绪的（反正刚开始我没有 思路 由于我们需要求一个最小权的，恰好有 need 条边的生成树 首先可以想到一个贪心的作法就是我先把最小的白边加入生成树之中直到 need 条跑...

MST 最小生成树板子 前言 今天对我的图论知识进行了一次的扩充，最小生成树 前言知识：并查集，可以去翻我的博客虽然还不完善但也有一点点的用途 kruskal 算法 思路 kruskal 算法由 kruskal 发明（废话），本质思想是在两个最小联通块之间找到最小的边使得这两联通快之间合并代价最小（就是边权 所以，kruskal 算法是一个贪心的做...

并查集 前言 今天根据书上的指引，想要学习最小生成树，然而蒟蒻在 OI WIKI 上学习的时候被告知： 前置章节是并查集。。。 于是蒟蒻便用了一天的时间 A 了三道黄题一道蓝题（其实相当于一道黄题…… 所以今天蒟蒻过来总结一番 定义 并查集是一种树形结构，通过名字我们可以知道： 并：合并，查：查询，集：集合 就是合并和查询一个集合 也可以相当于是联...

最近公共祖先 LCA 洛谷 P3379 今天 xiao 习了一下 LCA 过程十分曲折。。。 （检查的时候主函数没有调用 dfs，调试了好几遍才发现。。。 首先，我们先来看一看定义：最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 它有三种做法： 暴力 ...

P1827 奶牛 题目解读 其实说到底就是一道树的后序遍历反推而已嘛 首先，让我们看一遍题目： 给了一棵树的前序中序遍历，让求出后序遍历；（习惯性的打出分号 https://oi-wiki.org/graph/tree-basic/#_14（附上OI-WIKI的讲解 首先我们知道前序遍历在开头是根节点，那么，就将根节点取出（用 string 可做到...