积性函数和莫比乌斯反演

您也可以阅读体验更好、叙述更严谨的论文

积性函数

数论函数是指定义域在正整数、而值域在复数域上的一类函数,即\(f:\mathbb{Z}^{+}\rightarrow\mathbb{C}\)。

下文中的数论函数值域都在整数上。积性函数是一种特殊的数论函数,他们满足对于任意互质的一对数\(p,q\),有\(f(p)\cdot f(q)=f(pq)\),即他们的函数值乘起来等于他们乘起来的函数值。特别地,如果对于任意不互质两数上面的条件也成立,则称这个函数为完全积性函数

继续阅读“积性函数和莫比乌斯反演”

FHQ Treap

\(\text{FHQ Treap}\)是一种好写好用的平衡树。

它的平衡策略和普通\(\text{Treap}\)相似,采用在维护\(\text{BST}\)性质的同时维护随机的堆的形态来维持平衡;
但是维护结构的方式和\(\text{Treap}\)不同,不采用旋转,而是采用拆和合并的方法来维持树和堆的特性。

同时,由于\(\text{FHQ Treap}\)的操作所涉及的节点和基于旋转的其他平衡树相比少(仅\(\log n\)个),它支持可持久化

继续阅读“FHQ Treap”