0. 前置知识

需要提前有字典树的知识

1. 双数组字典树介绍

双数组字典树英文名为DoubleArrayTrie，他的特点就是使用两个数组来表示一颗字典树，这里有比较有趣了，两个数组是怎么表达出字典树的呢？

2. 双数组介绍

顾名思义，有两个数组，一个是base，另一个是check。

首先介绍数组的下标，数组的下标代表字典树上节点的编号，一个下标对应一个节点。

其实base数组的作用是用来记录一个基础值，这个值可以是随机值，只要不产生冲突就可以了，所以这个值可以用随机数算法获取，当然这样效率不高，高效的做法应该是使用指针枚举技术，ok，现在你已经明白了，base数组是一个不产生冲突的随机数组。

最后，check数组，check数组与base数组相互照应，如果base[i]=check[j] 则说明j是i的儿子，而且i到j的边权恰好为j-base[i]，也可以写作j-check[j]好好理解这句话

从另一个方面而言，双数组字典树的base数组，应该是一个指针数组，他指向了一个长度为字符集大小的数组的首地址，而check数组是一种hash碰撞思路，由于base数组疯狂指向自己，导致产生了很多碰撞，但是由于字典树是一个稀疏图，导致儿子节点指针利用率低，所以base数组疯狂复用这段空间，最后必须要依赖check来解决冲突，

双数组字典树相比于传统字典树，仅仅只在内存方面于增删改查占有优势，但是唯一不好的地方就是删和改会导致base数组内存分裂，难以回收，删和改如果占大头，那么传统字典树的内存效率更高

由于搜索领域几乎不涉及到删和改，所以这个数据结构很nice，字符集多大，就节省了多少倍的空间

数据结构很棒，但是在现在这个内存不值钱的时代，这些指针的储存用hashmap直接无脑顶掉，空间占用也高不了多少，hashmap顶多浪费两倍空间

两倍的空间算不上啥，除非这是唯一的优化点，否则不会优化到这个数据结构上来

分块

已知某函数$f(x)$对于$x\in[l,r]$，有$f(x)$关于$x$单调，且$f(x)$值域远小于$x$的定义域。

现在要你求$\sum_{x=1}^n g(x,f(x))$

那么我们就可以根据$f(x)$对$g$进行分块，在这一块中，始终有常数$y=f(x)$，然后对$h(x)=g(x,y)$统计$x$的前缀和。

最终我们就能很快的计算答案。

前言

关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？

前置知识

代数系统，群论

环

环是一个具有两个二元运算的代数系统。环$\lt R,+,\circ\gt$满足

• $\lt R,+\gt$构成交换群， 即$+$满足封闭性、结合律、单位元、逆元、交换律

• $\lt R,\circ\gt$构成半群， 即$\cdot$满足封闭性、结合律、单位元

• $\circ$对$+$有分配率，即$a\circ(b+c)=a\circ b+a\circ c$

集合论

集合论是群论的基础，群论是建立在集合论上的。

集合的基本操作

集合的交

$$
A \cap B = \lbrace x \vert x \in A \wedge x \in B \rbrace
$$

集合的并

$$
A \cup B = \lbrace x\vert x \in A \vee x \in B \rbrace
$$

集合的笛卡尔积

注意到笛卡尔积是一个二元组。
$$
A \times B = \lbrace (x,y) \vert x \in A \wedge y \in B \rbrace
$$

集合的映射

我们定义一个映射$f$满足 $f(x) = y $， 其中 $x\in A$， $y\in B$， 即映射可以把一个集合A中的元素映射到集合B中的一个元素。

可以称映射$f$作用于集合A，映射到集合B

克鲁斯卡尔重构树

有的时候，我们需要对最小生成树进行进一步的研究，比方说我们考虑最小生成树上任意两点路径的最小值，这个可以使用主席树、树剖等做法，
但是我们这样考虑，加入新的点，让边权变为点权，路径权的最小值就成了点权的最小值，如下图所示，最小生成树的点全部成为了克鲁斯卡尔重构树上的叶子，非叶节点充当了边权。

1
2
3
4
5
6
7

graph LR;
1((1))-- 5 ---2((2))
2((2))-- 4 ---3((3))
3((3))-- 3 ---4((4))
1((1))-- 8 ---4((4))
2((2))-- 7 ---5((5))
4((4))-- 2 ---6((6))