Believe it

相信不屈不挠的努力,相信战胜死亡的年轻

2020-03-16
- ACM
  - 学习笔记
    字符串
后缀树

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 后缀树一颗后缀树是针对一个字符串而言的，该后缀树能识别这个字符串的所有后缀，能且仅能识别这个字符串的所有字串，后缀树空间压缩常常我们会在后缀树的边上储存字符串，而不是字符，这样可以避免大量的内... 阅读全文…
2020-03-16
- ACM
  - 学习笔记
    字符串
trie

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 字典树字典树是我接触自动机的开端，我们先讲自动机，自动机自动机有五个要素，开始状态，转移函数，字符集，状态集，结束状态。自动机识别字符串假设我们有一个自动机，他长这个样子,他能识别字符串a... 阅读全文…
2020-03-16
- 数据结构
cartesianTree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # cartesian tree 笛卡尔树是一颗二叉树，他满足中序遍历为维护的序列，且满足堆的性质 build我们使用单调栈来维护树根到叶子的链，在单调栈的构建中完成树的构建 ct代码阅读全文…
2020-03-16
- 数据结构
VPTree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial vantate point treevp tree 是一颗二叉树，他和kd tree有着一定的相似度, 树上信息每一颗子树都要维护一个点集，对于每个节点，我们都维护一个距离d，然后将到该节点的距离小... 阅读全文…
2020-03-16
- 数据结构
scapegoateTree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # scapegoat Tree 替罪羊树，他是一个暴力的bst，与普通bst相比，他记录了子树的大小，用参数alpha来定义平衡，即左右子树的大小都不允许超过根的alpha倍，所以往往aplha是... 阅读全文…
2020-03-16
- 数据结构
无旋Treap

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial namedescirption inputoutputsample inputsample outputtoturialcode 阅读全文…
2020-03-16
- 数据结构
Treap

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Treap 树堆Treap来源于Tree+Heap的组合, 其实就是一棵树，他的节点储存了两个键，一个是我们维护的信息，另外一个是随机数，我们不妨设前者叫key，后者叫rand_key，Treap的... 阅读全文…
2020-03-16
- 数据结构
SplayTree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # splay tree 伸展树，以其操作splay出名。伸展树的本质就是bst， ## splay操作伸展树对splay操作的参数是一个节点，他的结果是将这个节点通过双旋变成根。 ## s... 阅读全文…
2020-03-16
- 数据结构
AATree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial AA Tree AA树真的很棒，虽然他没有普通红黑树那么厉害,但是AA树挺容易实现的，AA树是一棵右倾红黑树23树，注意! 这里是23树，不是234树。 AA树的由来 Arne Andersson教... 阅读全文…
2020-03-16
- 数据结构
LLRBTree

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial left leaning red black treeleft leaning red black tree定义在红黑树的基础上，左倾红黑树保证了3节点(2key-3son-node)的红色节点为... 阅读全文…