离散化与哈希

离散化

算法学习笔记(19): 离散化

离散化,就是当我们只关心数据的大小关系时,用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希,它在保持原序列大小关系的前提下把其映射成正整数。离散化的核心思想是将数据分布范围大但数量少(即稀疏)的数据进行集中化的处理,减少空间复杂度。

区间和

https://www.acwing.com/problem/content/description/804/

问题

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l, r] 之间的所有数的和。

$−10^9≤x≤10^9,1≤n,m≤10^5,−10^9≤l≤r≤10^9,−10000≤c≤10000$

时间复杂度分析

  1. 快排:$O((n+2m)log(n+2m))$
  2. 去重:$O(n+2m)$
  3. 二分:$O((n+2m)log(n+2m))$
  4. 前缀和:$O(n+2m)$

总复杂度为:$O((n+2m)log(n+2m))$

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
typedef pair<int,int> PII;
vector<PII> add, query; //存储插入和询问操作的数据
vector<int> alls; // 存储所有待离散化的数据
const int N = 3e5 + 10; // 将所有的x和询问区间的左右端点 均离散化到 a[1~N] 所以 N = n + 2*m
int a[N], s[N]; // 前缀和

int find(int x){ //返回的是输入的坐标的离散化下标
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = ( l + r )>> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 下标从1开始
}

int main(){
int n , m;
cin >> n >> m;
for(int i = 0; i < n; i++){
int x , c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x); //添加到待离散化序列
}
for(int i = 0; i < m; i++){
int l , r;
cin >> l >> r;
query.push_back({l, r});
alls.push_back(l); //左右端点添加到待离散化序列
alls.push_back(r);
}

// 排序+去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

for(auto item:add){ // add 操作
int x = find(item.first);
a[x] += item.second;
}

for(int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];

for(auto item:query){ // query 操作
int l = find(item.first);
int r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}

Hash

Hash 表又称为散列表,一般由Hash函数(散列函数) 与链表结构共同实现。与离散化思想类似,当我们要对若干复杂信息进行统计时,可以用Hash 函数把这些复杂信息映射到一个容易维护的值域内。因为值域变简单、范围变小,有可能造成两个不同的原始信息被Hash函数映射为相同的值,所以我们需要处理这种冲突情况。

下面通过一道例题给出两种处理冲突的方法。

模拟散列表

https://www.acwing.com/problem/content/842/

题目

维护一个集合,有两种操作:I x ,插入一个数 x,Q x 询问x是否在集合中出现过,进行n次操作,对于每个询问输出对应的结果。

$1 <= n <= 10^5, -10^9 <= x <= 10^9。$

拉链法

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
const int N = 100003; // 为大于1e5的最小素数
int n, h[N], e[N], ne[N], idx;

void insert(int x){
int k = (x % N + N) % N; // 保证结果为正
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}

bool query(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x) return true;
}
return false;
}


int main(){
memset(h, -1, sizeof h);
scanf("%d", &n);
while(n--){
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'I') insert(x);
else{
if(query(x)) puts("Yes");
else puts("No");
}
}
return 0;
}

开放寻址法

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
const int N = 200003, null = 0x3f3f3f3f; // 空间为范围的两到三倍
int n, h[N];

int find(int x){
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x){
k++;
if(k == N) k = 0;
}
return k;
}

int main(){
memset(h, 0x3f, sizeof h);
scanf("%d", &n);
while(n--){
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find(x);
if(*op == 'I') h[k] = x;
else{
if(h[k] != x) puts("No");
else puts("Yes");
}
}
return 0;
}

雪花

https://www.acwing.com/problem/content/139/

问题

有 N 片雪花,每片雪花由六个角组成,每个角都有长度。第 i 片雪花六个角的长度从某个角开始顺时针依次记为$a_{i,1}, a_{i,2},…,a_{i,6}$ ,因为雪花的形状是封闭的环形,所以从任何一个角度开始顺时针或逆时针往后记录长度,得到的六元组都代表形状相同的雪花。例如 $a_{i,1}, a_{i,2},…,a_{i,6}$ 和 $a_{i,2}, a_{i,3},…,a_{i,1}$ 就是相同的雪花。我们称两片雪花形状相同,当且仅当它们各自从某个角开始顺时针或逆时针记录长度,能得到两个相同的六元组。 求这 N 片雪花中是否存在两片形状相同的雪花。

$1≤N≤100000, 0≤a_{i,j}<10000000$。

分析

定义 Hash 函数 $H(a_{i,1}, a_{i,2},…,a_{i,6}) =( {\textstyle \sum_{j=1}^{6}}a_{i,j} + {\textstyle \prod_{j=1}^{6}}a_{i,j})mod P$ , 其中 P 为最接近 N 的质数。显然,对于两片形状相同的雪花,它们六个角的长度之和、之积都相等,因此它们的Hash 函数值也相等。

期望时间复杂度为 $O(N)$

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
typedef long long ll;
const int N = 100003; //
int h[N], e[N][6], ne[N], idx, n;

int H(int a[]){
int sum = 0, mul = 1;
for(int i = 0; i < 6; ++ i){
sum = (sum+a[i])%N;
mul = (ll)mul*a[i]%N;
}
return (sum+mul)%N;
}

bool Equal(int a[], int b[]){ // 复杂度为 6*6 但Hash值相等的概率很低,可以忽略
for(int i = 0; i < 6; ++ i){
for(int j = 0; j < 6; ++ j){
bool eq = true;
for(int k = 0; k < 6; ++ k){ //顺序相同
if(a[(i+k)%6] != b[(j+k)%6]) eq = false;
}
if(eq) return true;
eq = true;
for(int k = 0; k < 6; ++ k){ //顺序相反
if(a[(i+k)%6] != b[(j-k+6)%6]) eq = false;
}
if(eq) return true;
}
}
return 0;
}

bool insert(int a[]){
int v = H(a); // 得到hash值,地址
for(int i = h[v]; i != -1; i = ne[i])
if(Equal(e[i], a)) // 判断序列顺序是否相等
return true;
memcpy(e[idx], a, 6*sizeof(int)); // 未找到形状相同的雪花,执行插入
ne[idx] = h[v];
h[v] = idx ++;
return false;
}

int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n; ++ i){
int a[10];
for(int j = 0; j < 6; ++ j) cin >> a[j];
if(insert(a)){
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
system("pause");
return 0;
}

字符串哈希

下面介绍的字符串Hash函数把一个任意长的字符串映射成一个非负整数,并且其冲突的概率几乎为零。

取一固定值 P , 把字符串看作 P 进制数,并分配一个大于 0 的数值,代表每种字符。 一般来说,我们分配的数值都远小于 P 。例如,对于小写字母构成的字符串,可以令 a = 1, b = 2, … , z = 26。固定值 M , 求出该P 进制对 M 的余数,作为该字符串的 Hash 值。 一般来说, 我们取 P = 131 或者 P = 13331, 此时 Hash 值 产生冲突的概率极低, 只要 Hash 相同,我们就可以认为原字符串是相等的。通常我们取 $M = 2^{64}$ ,即直接使用 unsigned long long 类型 存储这个 Hash 值,在计算时不处理算数溢出问题,产生溢出时相当于自动对 $2^{64}$取模,这样可以避免低效的取模运算。

对于一个长度为$l$的字符串s来说,我们可以这样定义多项式 Hash 函数:
$$
f(s) = {\textstyle \sum_{i=1}^{l}s[i] \times b^{l-i}} (mod M)
$$
例如,对于字符串xyz, 其哈希函数值为 $xb^{2} + yb + z$。 特别需要说明的是,也有很多人使用的是另一种 Hash 函数的定义, 即$f(s) = {\textstyle \sum_{i=1}^{l}s[i] \times b^{i-1}} (mod M)$,这种定义之下,同样的字符串 xyz 的哈希值就变为了 $x + yb + zb^2$ 了。

https://www.acwing.com/problem/content/description/843/

题目

给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 l1,r1,l2,r2,请你判断 [l1,r1][l2,r2] 这两个区间所包含的字符串子串是否完全相同。

$1≤n,m≤10^5$

分析

定义哈希函数 $h(s) = {\textstyle \sum_{i=1}^{l}s[i] \times p^{l-i}} (mod M)$ ,则子串s(L~R)的哈希值 $h(s(l,r)) = h(s(1,r)) - h(s(1,l-1))\times p^{r-l+1} $ 。

代码

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
typedef unsigned long long ULL;
const int N = 100010, P = 131;
ULL h[N], p[N];
int n, m;
char str[N];

ULL get(int l, int r){ // 得到子串的哈希值
return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){
scanf("%d%d%s", &n, &m, str+1);
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
}
while(m--){
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}

回文子串的最大长度

https://www.acwing.com/problem/content/description/141/

题目

询问长度为n的字符串S的最长回文子串的长度。

$1<= n <=10^6$

分析

回文串的长度为奇数或者偶数,可将其分为两类奇串和偶串,于是我们可以枚举字符串S的回文子串的中心位置 i = 1~ n , 观察从中心位置出发向左右两侧最长可以扩展出多长的回文串,有:

  1. 求一个最大的整数 r 使得 S[i-r ~ i-1] = reverse(S[i+1 ~ i+r]) ,那么以 i 为中心的最长奇回文子串的长度就是 $2\times r +1$。
  2. 求一个最大的整数 r 使得 S[i-r~ i-1] = reverse(S[i ~ i+r-1]) , 那么以 i 为中心的最长偶回文子串的长度为 $2\times r。$

当 r 为可行解(r>1)时,r-1一定为可行解, 故我们可以二分求出 r 。

时间复杂度为 $O(nlogn)$。

代码

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
39
40
41
42
43
44
45
46
// 回文子串的最大长度
using namespace std;
const int N = 1e6 + 10, P = 131;
typedef unsigned long long ull;
ull p[N], f1[N], f2[N];
char str[N];

inline ull H1(int l, int r){
return (f1[r]-f1[l-1]*p[r-l+1]);
}

inline ull H2(int l, int r){
return (f2[l]-f2[r+1]*p[r-l+1]);
}

int main(){
int T = 1;
p[0] = 1;
for(int i = 1; i <= N; ++ i) p[i] = p[i-1]*P; // 初始化
while(cin >> str+1, strcmp(str+1, "END")){
int n = strlen(str+1);
for(int i = 1; i <= n; ++ i) f1[i] = f1[i-1]*P + str[i]- 'a' + 1;
f2[1+n] = 0; // 初始化
for(int i = n; i >= 1; -- i) f2[i] = f2[i+1]*P + str[i] - 'a' + 1;
int ans = 0;
for(int i = 1; i <= n; ++ i){
int l = 0, r = min(i-1, n-i); // 奇数
while(l < r){
int mid = (l + r + 1) >> 1;
if(H1(i-mid, i-1) == H2(i+1, i+mid)) l = mid;
else r = mid - 1;
}
ans = max(ans, 2*l+1);
l = 0, r = min(i-1, n-i+1); // 偶数
while(l < r){
int mid = (l + r + 1) >> 1;
if(H1(i-mid, i-1) == H2(i, i+mid-1)) l = mid;
else r = mid - 1;
}
ans = max(ans, 2*l);
}
printf("Case %d: %d\n", T++, ans);
}
system("pause");
return 0;
}

unordered_map

unordered_map是C++中的哈希表,可以在任意类型与类型之间做映射。

基本操作

  1. 引用头文件(C++11):#include
  2. 定义:unordered_map<int,int>、unordered_map<string, double> …
  3. 插入:例如将(“ABC” -> 5.45) 插入unordered_map<string, double> hash中,hash[“ABC”]=5.45
  4. 查询:hash[“ABC”]会返回5.45
  5. 判断key是否存在:hash.count(“ABC”) != 0 或 hash.find(“ABC”) != hash.end()
  6. 遍历
1
2
3
4
for (auto &item : hash)
{
cout << item.first << ' ' << item.second << endl;
}

1
2
3
4
for (unordered_map<string, double>::iterator it = hash.begin(); it != hash.end(); it ++ )
{
cout << it->first << ' ' << it->second << endl;
}

进阶操作

如果想让自定义的class作为key(unordered_map<key,value>)来使用unordered_map,需要实现:

(1) 哈希函数,需要实现一个class重载operator(),将自定义class变量映射到一个size_t类型的数。一般常用std::hash模板来实现。
(2) 判断两个自定义class类型的变量是否相等的函数,一般在自定义class里重载operator==
示例代码:

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
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Myclass
{
public:
int first;
vector<int> second;

// 重载等号,判断两个Myclass类型的变量是否相等
bool operator== (const Myclass &other) const
{
return first == other.first && second == other.second;
}
};

// 实现Myclass类的hash函数
namespace std
{
template <>
struct hash<Myclass>
{
size_t operator()(const Myclass &k) const
{
int h = k.first;
for (auto x : k.second)
{
h ^= x;
}
return h;
}
};
}

int main()
{
unordered_map<Myclass, double> S;
Myclass a = { 2, {3, 4} };
Myclass b = { 3, {1, 2, 3, 4} };
S[a] = 2.5;
S[b] = 3.123;
cout << S[a] << ' ' << S[b] << endl;
return 0;
}

输出

1
2.5 3.123

练习

  1. hash https://www.acwing.com/problem/content/142/
  2. hash https://www.acwing.com/problem/content/158/
  3. map https://www.acwing.com/problem/content/description/1525/
  4. hash https://codeforces.com/contest/1200/problem/E
  5. 2020CCPC威海G(hash+线段树)https://codeforces.com/gym/102798
  6. 离散化 https://ac.nowcoder.com/acm/skill/detail/acm/1591
  7. 离散化 https://www.acwing.com/problem/content/123/
  8. 二维离散化 https://www.acwing.com/problem/content/description/123/

参考

  1. https://www.nowcoder.com/discuss/178326?type=101
  2. https://www.cnblogs.com/G-H-Y/p/14327856.html
  3. 算法竞赛进阶指南(李煜东)
  4. https://zhuanlan.zhihu.com/p/112497527
  5. https://oi-wiki.org/string/hash/
  6. 区间和 https://www.acwing.com/solution/content/13511/
  7. 二维离散化 https://zhuanlan.zhihu.com/p/126538872
  8. unordered_map 转载 https://www.acwing.com/blog/content/9/