树剖 一个神奇的数据结构 树链剖分，顾名思义就是把一棵树解剖成一些链 我们先来几个定义： 重儿子：对于一个节点来说，他的儿子们中子树体积最大的儿子称为他的重儿子 重边：两个重儿子连起来的边 重链：很多条重边连起来形成的一条链 轻儿子：除了重儿子之外的儿子 轻链：类比一下 我们会发现，重儿子是可以一遍dfs求出来的，我们会发现一个很重要的性质： 在d...

主席树 全称为：可持久化线段树 我们考虑一件事情，如果说我们对于一个线段树来说，希望它可以查询一些修改之前的序列（我们称之为历史版本） 我们当然可以每一次把线段树复制一遍，但是时空复杂度并不能够接受 所以我们应该进行一些可持久化的处理： 我们发现对于单点修改来说，线段树最多改变的就是log2n个节点 所以我们可以把更改的几个节点单独拿出来存储起来，...

分块大法好啊 分块，顾名思义，就是一种把序列分成若干个块的算法（数据结构） 前段时间的时候写的分块，调到怀疑人生，结果今天开始学主席树了发现我爱分块 分块的思想简称就是：大块维护，小块朴素 P3396 哈希冲突 我们先假设一下，如果说模数是小于等于n\sqrt{n}n​的时候，我们是不是可以预处理出来所有模数对应的答案（更改很容易的） 然后我们再想...

被迫营业，学习了树状数组 树状数组 粗： 树状数组是一个基于二进制的数据结构，我们将每一个值存为区间右端点的一个“lowbit”长度的区间中，就构成了树状数组（真的是很粗。。。） 细：简介 首先，树状数组这个数据结构可以动态维护区间和，支持单点修改区间查询（其实还支持区间修改单点查询或者都一起支持，这个后续再讲，因为是扩展内容） 在学习快速幂算法的...

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