数学 (科普)
1. 求导
定义
$ f{}’(x)=\lim_{\Delta x\rightarrow 0}\frac{f(x+ \Delta x)-f(x)}{\Delta x} $
公式
$ (x^{\alpha})’=\alpha x^{\alpha-1} $
$ (e^x)’=e^x $
$ (\ln x)’ = \frac{1}{x} $
$ (sin(x))’=cos(x) $
$ (a^x)’=a^x \ln a $
$ (f(x)+g(x))’=f’(x)+g’(x) $
$ (f(x)-g(x))’=f’(x)-g’(x) $
$ (f(x)g(x))’=f’(x)g(x)-g’(x)f(x) $
$ (f(x)/g(x))’=\frac{f’(x)g(x)-g’(x)f(x)}{g^2(x)} $
链式法则
导数求最值
多元函数求偏导
例题
最小二乘法
(没听懂)
2. 积分
定义
若有 $F’(x)=f(x) $
则有 $ \int_{l}^{r}f(x)dx=F(b)-F(a) $
使用
杜教筛复杂度证明
调和级数
$ \sum_{i=1}^{n} O(\frac{1}{n}) = ? $
$ \sum_{n=1}^k \, \frac{1}{n} \;>\; \int_1^{k+1} \frac{1}{x}\,dx \;=\; \ln(k+1). $
3. 概率与期望
见PDF
数据结构
1. 莫队
PS:(我也不知道为啥这个算数据结构)
要求
若已知 $ [L,R] $ 的信息,可快速求出 $ [L+-1,R] $ 和 $ [L,R+-1] $ 的信息
离线
只有询问
时间复杂度 $ O(n\sqrt n) $
例题
在线
(即为分块。。)
2. 莫队扩展
带修莫队
做法
设 $ siz=n^{\frac{2}{3}} $ 或 $ siz=n^{\frac{1}{3}} $
对询问按 $ (l/s,r/s,t) $ 排序
乱搞
复杂度 $ O(n^{\frac{5}{3}}) $
在线
(即为分块。。)
(莫队上树)树上莫队转为DFS序后在DFS序上莫队
in(a)表示点a在进入DFS序的第一个位置以 $ (in(a)/s,in(b)) $ 排序