二维哈希
有了一维哈希的基础知识,很容易就能联想到二维哈希。那具体又该如何实现呢?
前置知识
我们先回顾下二维前缀和的求解方法, 设b为二维差分数组, a为原数组, 则:
b [i] [j] = b[i - 1] [j] + b[i] [j -1] - b[i -1] [j - 1] + a[i] [j]
这里理解的话, 用面积类比元素和, 则b[i] [j] 表示(1, 1, i, j)所围成矩形的面积,减去重复的即可。
于是我们就有了预处理二维前缀表的方法
代码如下:
for (int i = 1; i <= n; ++i)//n行m列的矩阵
for (int j = 1; j <= m; ++j)
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
查询也比较简单,证明与上述类似,画个图就出来了 复杂度 O(1)
代码
int ask(int x1, int y1, int x2, int y2)//视情况开long long
{
return b[i][j] - b[i - 1][j] - b[i][j - 1] + b[i - 1][j - 1];
}
二维哈希表的预处理
参考下一维哈希表的预处理方法, 我们对二维哈希的预处理有如下步骤
h[i] [j] = 表示 (1, 1, i, j)子矩阵的哈希值
1.
先按照一维哈希表的方式处理出每一行的哈希值,即此步处理完成后h [ i ] [ j ]表示第i行(1, j)字串的哈希值
2.
接下来就是, 把一行缩成一个点那么(1, 1,i, j)就被缩成了j个在纵向上的点, 于是这又转化为一维哈希表的处理,又因为我们提前计算了h[i - 1] [j], h[i] [j] 的值, 那么更新 h[i] [j]的公式: h[i] [j] += h[i-1] [j] * base
代码如下
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
scanf("%d", &x);
h[i][j] = ((ull)h[i][j - 1] * 131 + x);
}
//第一步获得每行子串的哈希表
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
h[i][j] = (h[i][j] + (ull)h[i - 1][j] * 233);
//第二步获得子矩阵的哈希值
注意:这里我选择了121和233,是为了减少哈希冲突的概率(呸,提高我们的AC率)。其次, 我这次并没有模大质数而是选择了自然溢出。其实自然溢出相当于电脑自动帮你mod 2^64 (unsigned long long) ,有利于代码书写,一定程度上节省取模的时间。不过由于自然溢出模的质数是固定的,(会被用心良苦的毒瘤出题人卡)
一般为了保险会双哈希(即选择两个进制数)。
二维哈希表的查询操作
目标: 查询子矩阵 (x1, y1, x2, y2) 的哈希值
联系一维哈希表的预处理和二维哈希表的预处理以及二维前缀表的知识,我们很容易 得到查询子矩阵哈希值的公式:
其中 base1 表示行哈希处理时选用的进制数, 也就是步骤1选择的进制数,base2表示列处理的进制数,也就是步骤2选择的进制数。别看这个公式复杂,整体上就是套用了二维前缀表查询的公式再乘上一些base, 而这些base又与一维哈希的查询息息相关,那么整个公式的条理也就清楚了。相关的证明与一维哈希查询类似,但比较繁琐,故从理解的方式简要说明了这个公式。
总结
在一维哈希中,我们是将长度为n的序列哈希成长度为n的一个P进制数,高位在前。
预处理:行哈希,列哈希
公式推倒(呸, 是推导hh)
1.
预处理矩阵 n * m 的矩阵每一行的哈希值
2.
求 a * b矩阵哈希值
设右下角坐标为(i, j)的 a * b的矩阵的哈希值为 H[i] [j]
矩阵每一行的b个元素的哈希值可以由一维哈希的方法求出为h[k] [j - b + 1], k 属于 [i - a + 1, i]
则其对应的第 i + 1行的 a * b矩阵的哈希值 H[i + 1] [j]可以由矩阵的所有元素向高位移动b位,
再加上第 i + 1行的哈希值, 然后减去第i 个矩阵的第一行的哈希值得到
为啥最后要减的时候乘上 p^ab捏😁
相信看到这里,对于二维哈希应该有了初步的了解, 其实也是复习了一遍,如果没有人问的话, 我可能已经忘了,害,说多了都是泪,菜还是那么菜