扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ （这里以实际运行效果估计，实际复杂度据说和洲阁筛一样）求出一般积性函数的前缀和，消耗 $O(\sqrt{n})$ 的空间。

矩阵树定理的学习笔记和部分线性代数的知识，记录三道经典题目及变元矩阵树定理。

在 OI 中，我们手写的数据结构几乎都是静态内存的，而 STL 中的容器由于内存动态化的原因在做题中容易 TLE，这里介绍几种常见容器静态化内存的方法。

作为一个先学工程的蒟蒻 oier，也就只能在卡常上有一些技巧了……

然而我太弱，并没有去成 WC，虽然感觉 T2 卡三级缓存不是应该很好卡吗？

这里总结松爷的一些技巧和记录一些其他技巧及一些实际例子。

Link-Cut Tree学习总结

在数据结构中有一类问题叫做动态树问题（DynamicTree），它会要求你对一颗树进行切割和拼接，然后再在上面维护传统的数据结构能维护的值，为了完成这一类问题，就有了很多相应的算法来解决这类问题，Link-Cut Tree 就是其中一种比较方便实用的算法。

这里保存一些后缀自动机常见应用和例题，不断完善中，更多的还是看补档计划吧……

后缀自动机学习总结

前置技能

有限状态自动机

有限状态自动机 DFA，功能就是识别字符串，令一个自动机 $A$，若能识别字符串 $S$，就记为 $A(S) = true$，否则 $A(S) = false$。自动机由五个部分组成，$alpha$ 为字符集，$state$ 状态集合，$init$ 初始状态，$end$ 结束状态集合，$trans$ 状态转移函数。

$tarns(s, ch)$ 表示当前状态是 $s$，在读入后字符 $ch$ 后所到达的状态；同时 $tarns(s, str)$ 表示当前状态是 $s$，在读入后字符串 $str$ 后所到达的状态。

如果 $trans(s, ch)$ 这个转移不存在，我们设其为 null，同时 null 只能转移到 null，null 表示不存在的状态。

有上下界的网络流。
$(u, v)$ 为一条边，$s$ 为源，$t$ 为汇，$S$ 为超级源，$T$ 为超级汇，$d$ 记录下界和。

数论函数：定义域为正整数的函数。

积性函数

定义

积性函数：对于任意两个互质的正整数 $a,b$ ，均满足 $f(ab)=f(a)f(b)$ 的函数 $f$

完全积性函数：对于所有正整数 $a,b$ ，均满足 $f (ab) = f (a) f (b)$ 的函数 $f$

定义逐点加法： $(f + g)(x) = f(x) + g(x)$，$(f \cdot g)(x) = f(x)g(x)$

在进行算法设计时，我们常用的两种线性数据结构是数组和链表。它们各有优缺点。数组特点是元素在内存中紧挨着存储，因而优点是定位快 $O(1)$，缺点是插入删除慢 $O(n)$；而链表则不同，它通过指针将不同位置的元素链接起来，因而优缺点与数组正好相反：定位慢 $O(n)$，插入删除快 $O(1)$。而块状链表，它将数组和链表的优点结合来，各种操作的时间复杂度均为 $O(\sqrt n)$。

树堆，在数据结构中也称 $Treap$，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 $O( \log n )$。

相对于 $AVL$ 和红黑树，其实现简单，相对于 $Splay$，其效率更高，相对于替罪羊和 $SBT$，其适用范围更广(尤其是非旋转式Treap)。

不完全模板如下，长期更新中(已弃):

静态内存指针版动态开点线段树…(这名字有毒)

自行修改 $pushDown$ 和 $update$ 等…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct Node {
    Node *lc, *rc;
    int l, r;
    long long val;
    int tag;
    inline void clear() { val = tag = 0; }
    inline void cover(const int delta) { tag += delta, val += (long long)delta * (r - l + 1); }
    inline void pushDown() { if (tag) lc->cover(tag), rc->cover(tag), tag = 0; }
    inline void update(const int l, const int r, const int delta) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) cover(delta);
        else pushDown(), lc->update(l, r, delta), rc->update(l, r, delta), val = lc->val + rc->val;
    }
    inline long long query(const int l, const int r) {
        register long long ret = 0;
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return val;
        else return pushDown(), ret += lc->query(l, r), ret += rc->query(l, r), ret;
    }
} pool[(MAXN + 10) << 4], *root, *tail = pool;
inline void build(Node *&rt, const int l, const int r, int *a) {
    rt = tail++, rt->clear(), rt->l = l, rt->r = r;
    if (l == r) { rt->val = a[l]; return; }
    register int mid = l + r >> 1;
    build(rt->lc, l, mid, a), build(rt->rc, mid + 1, r, a);
    rt->val = rt->lc->val + rt->rc->val;
}

质数,欧拉函数及莫比乌斯函数的快速线性筛选法，时间复杂度 $O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const int MAXN = 100000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
    mu[1] = phi[1] = 1;
    for (register int i = 2; i <= MAXN; i++) {
        if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
        for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
        }
    }
}

$AA$ 树是 $Arne Andersson$ 教授在他的论文 $”Balanced search trees made simple”$ 中介绍的一个红黑树变种，设计的目的是减少 $RB$ 树考虑的 $cases$。

通常情况下，我们可以使用函数 $toupper()$ 和 $tolower()$ 来实现字母大小写的转化，但在需要常数优化的情况下，这是较慢的。

定义

字符串

字符串 $s$ 连续的一段字符组成的串叫做字符串，更广义地，任何一个由可比较大小的元素组成的数组都可称为字符串。字符串的下标从 $0$ 开始，长度为 $length(s)$。

后缀

后缀：$suffix(i)$ 表示字符串 $s$ 从第 $i$ 个位置开始的后缀，即由 $s[i]$ ~ $s[n - 1]$ 组成的子串。

Splay Tree（伸展树）是一种自平衡二叉排序树，可以在均摊 $O({\log} n)$ 的时间内完成基于 Splay（伸展）操作的修改与查询。

替罪羊树学习总结[模板]

传说中效率极高且较为好写的平衡树(抛开丧心病狂的红黑树和veb树)，替罪羊树写法相当暴力，不用旋转，它只会选择性地重新构树来保证复杂度。

树链剖分学习总结

如果要在一棵树上进行路径的修改,求极值,求和，似乎线段树即可完成，实际上只用线段树并不能很好的做到，只有用一种高级的东西——树链剖分。

概念

树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。
记size[v]表示以v为根的子树的节点数，depth[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，father[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置。只要把这些东西求出来，就能用$O(logn)$的时间完成原问题中的操作。

树上操作学习总结

储存

用邻接表储存。

1
2
3
4
5
6
7
8
9
10

const int MAXN = 10010;
struct Node {
    int v, w;
    Node(int v, int w) : v(v), w(w) {}
};
vector<Node> edge[MAXN];
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(Node(v, w));
    edge[v].push_back(Node(u, v));
}

KMP算法学习总结

KMP（Knuth-Morris-Pratt）是一种改进的字符串匹配算法，也是算法竞赛中常用的字符串匹配算法之一，它可以有效地利用失配信息来使得匹配全过程中不回溯，从而在线性时间内完成匹配。

字符串Hash学习总结

定义

字符串Hash简单来说就是：把字符串有效地转换为一个整数。

Hash函数

就是使得每一个字符串都能够映射到某一个整数上的函数

A*算法学习总结

引入

假设有人想从A点移动到一墙之隔的B点，如下图，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。

简化搜索区域

如上图，搜索区域已经划分成了方格，像这样简化搜索区域，是寻路的第一步。这一方法将搜索区域简化成了二位数组(基本的图论模型)，数组的每一个元素是是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从s到t我们经过的方块的集合。一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。

博弈论学习总结

Nim游戏

Nim游戏就是经典的取石子游戏，规则如下：
桌子上有 N 堆石子，游戏者轮流取石子。每次只能从一堆中取出任意数目的石子，但不能不取。 取走最后一个石子者胜。

结论：对于一个nim游戏局面($a_1,a_2, \cdots ,a_n$)，若$a_1$ ^ $a_2$ ^ \cdots ^ $a_n = 0$ 则先手必败。

数位dp模板，记忆化搜索，dp[pos][pre][status]。
以不要62【hdu】为例

两个n次多项式相加最直接的方法所需时间为O(n)，但是相乘最直接的方法所需时间为O(n²)。
快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 O(n log n)时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法，在 OI 中的主要应用之一是加速多项式乘法的计算。

pb_ds库

pb_ds??
平板电视??
pb_ds是G++编译器默认附带的一个扩展库,全称是Policy-Based Data Structures(官方传送门)…
pb_ds库里含有许多数据结构,如HashTable,trie,rb_tree,priority_queue…

SPFA

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

Dijkstra

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

树状数组求逆序对

树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree) 是一个查询和修改复杂度都为 $O(\log n)$ 的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；
经过简单修改可以在 $O(\log n)$ 的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。