Co老师也太强了吧 ！！！
ST 表
ST 表是基于 倍增 思想，用于解决 可重复贡献问题 的数据结构。
什么是可重复贡献问题？
可重复贡献问题 是指对于运算 ，满足 ，则对应的区间询问就是一个可重复贡献问题。例如，max 有 , gcd 有 ，所以区间最大值或最小值、区间 GCD 就是一个可重复贡献问题。可重复地意思是指，假设已经知道了一个区间的两个子区间（可重叠）的答案，且这两个子区间的并集包含该区间，则可由这两个子区间的答案，快速计算出该区间的答案。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次。另外， 还必须满足结合律 才能使用 ST 表求解。
综上想要使用 ST 表，需具备以下条件：
-
- 区间重叠不影响答案的正确性
-
例1
来看一道模板题吧~
https://www.luogu.com.cn/problem/P3865
解1
补充常识：
mx[i][j] 的含义：起点为 ，长度为 的区间的最大值。
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
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define N 100008
using namespace std;
int mx[N][20];
inline int read()
{
int x = 0,f = 1;
char ch = getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline int getmx(int l, int r){
int len = r - l + 1;
int t = (int)log2(len);
return max(mx[l][t], mx[r - (1 << (t)) + 1][t]);
}
int main(){
int n, m;
n = read(); m = read();
for(int i = 1; i <= n; ++i) mx[i][0] = read();
for(int j = 1; j <= log2(n); ++j)
for(int i = 1; i <= n - pow(2, j) + 1; ++i)
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
while(m--){
int l = read();
int r = read();
printf("%d\n", getmx(l, r));
}
return 0;
}
|
数论初步 （约数相关）
素数与合数
素数 的约数只有 和
既不是素数，也不是合数
算数基本定理
内容
如果不考虑排列次序的话，每个大于1的自然数都只能有一种方式分解成若干个（大于等于 1 个）素数的乘积。
性质
1.（存在性）每个大于 1 的自然数都可以分解成素数的乘积。
2.（唯一 性）这种分解，再不考虑排列次序的意义下，是唯一的。
约数与倍数
对于 如果 称 是 的公约数。对于其中最大的 ，称 是 的最大公约数，记为
对于 如果 称 是 的公倍数。对于其中最小的 ，称 是 的最小公倍数，记为
集合含义
，
GCD ：
LCM ：
除法
对于整数 ，存在唯一的两个整数 使得：
带余除法
=
整除
记做 ，此时也称 是 的倍数， 是 的约数。
性质
-
-
-
一些常用的复杂度常识
素数分布：
调和级数：
