标签:学习笔记

4 篇文章

zkw线段树 学习笔记
前置知识 C++位运算学过线段树(其实关系不大) 什么是zkw线段树 就是一种线段树。(废话) 与普通线段树相比,zkw线段树更快、更短小。 本篇博客讲一个例题:Luogu P3372 普通线段树 zkw线段树 zkw线段树的实现 首先来看一看变量的定义与BuildTree操作 这是一棵求和的线段树(废话) 然后我们发现它有16个叶子节点。 而$1…
主席树(静态) 学习笔记
在学习主席树之前 你必须学习: 线段树。 前缀和。 sort函数、unique函数以及lower_bound函数的使用方法。 什么是主席树 主席树又叫函数式线段树,又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。 主席树的模板 由于主席树比较难理解,所以结合代码理解一下: [crayon-…
fhq treap 学习笔记
序 今天心血来潮,来学习一下fhq treap(其实原因是本校有个OIer名叫fh,当然不是我) 简介 fhq treap 学名好像是“非旋转式treap及可持久化”。。。听上去怪怪的。其实就是可以代替LCT、BST等等码量很高的东东。 定义 [crayon-5db0730da12ae641565598/] 操作 最基本的操作 其实都不应该叫做操作…
矩阵快速幂 学习笔记
举例1:Fibonacci 题目传送门 题意 $$f[1]=1,f[2]=1,f[3]=2,f[4]=3 \dots f[n]=f[n-1]+f[n-2]$$那么输入$n$、$m$,求第n项Fibonacci的值$mod$ $m$,即$f[n]$ $mod$ $m$。$$1\leq n \leq 2 \times 10^9$$因为:$$f[i]=1…