字符串哈希模板

假设一个字符串的范围是[1,n]$[1,n]$,然后从中选择一个位置x,使得字符串分成两部分[1,x],[x+1,n],$[1,x],[x+1,n],$两个串的哈希值分别为x,y$x,y$,那么将后面的串移动到前一个串的前面的哈希值为x+y×px$x+y\times p^x$
——————————————————————————————————————————————————————————————————————
学了一天的字符串哈希，还是不怎么懂，下面写出来我的一些微薄的理解。

模板等做题了再贴！

翻了很多博客，发现就是没人介绍关于求区间字串的哈希值的方法，希望有大佬能为萌新解答一下。

经过hash$hash$处理后，在哈希数组h$h$中，单个的hash[i]$hash[i]$表示的不仅仅是简单的前缀和，这与前面乘的系数p$p$有关。

又发现了一个规律：hash[i,j]$hash[i,j]$区间的值其实就是s[i]∗p(j−i)+s[i+1]∗p(j−i−1)+.....+s[j];$s[i]\ast p^{(j-i)}+s[i+1]\ast p^{(j-i-1)}+.....+s[j];$

举个例子，hash(2,4)$hash(2,4)$就是s[2]∗p2+s[3]∗p+s[4]$s[2]\ast p^2+s[3]\ast p+s[4]$

当确定一个区间的哈希值的时时候,假设当是[lL,R],那么如果R变大,那么整体哈希值的变化就是先乘上种子p,然后再加上R+1的值,如果是区间减少变成[L+1,R]那么哈希值的变化就是减去L对应这一位的哈希值
—————————————————————————————————————————
2018年4月24日更新

发现了一个哈希+线段树的题目，这里就要求区间的合并，于是去推了下公式，hash(i,j)=hash[i,k]∗seed(j−k+1)+hash[j,k];$hash(i,j)=hash[i,k]\ast see{d}^{(j-k+1)}+hash[j,k];$

—————————————————————————————————————————
2018年4月28日更新

今天又学到了一种骚操作——如何计算将原字符串改变若干个字母后的哈希值。（不过有一个限制，就是在求字符串的哈希是，只有一个变量，而不是开了一个数组记录每一位的哈希值）

公式推就不推了，只是记录下公式结果：
首先明确字符串下标从1开始，字符串长度是len,改变的元素是s[i],将s[i]要改为c

h=h+(c−s[i])∗p(len−i);$h=h+(c-s[i])\ast p^{(len-i)};$