哈希问题的一类技巧

浅谈处理哈希问题的一类方法-线段树维护哈希

前言

一个初三蒟蒻粗浅的认知和总结，dalao不喜勿喷。分享的题也大都很水，仅是代表浅层理解。
简介/概括

哈希是一种常用的算法。我们在oi中使用哈希的主要目的是将难以直接处理、维护、比较的对象映射到范围小/便于维护/便于处理/便于比较的对象上。
映射的方式是哈希函数 $hash(x)$,设计哈希函数时会考虑对象的特性，并尽可能避免冲突。
通常，我们时常会把研究对象映射到整数上，这样就会出现溢出的问题，解决方法无非就两种：
1.自然溢出

就是不管它，让它自行溢出，根据溢出值来比较。仅限于long long类型。
2.双哈希

同时设计两种不同哈希函数进行维护。可大幅提升准确率，减少冲突概率。
字符串哈希

哈希里面比较常见的一种，就是把一个字符串看成一个 $n$ 进制数，把字符串弄成一个类似键值的东西。
对字符串作哈希后，可以进行高效的比较、取子串等操作，有时还会用线段树去维护它（一般带修）。
总而言之，字符串哈希是处理字符串问题的一种常见思路。
CF580E Kefa and Watch

题意描述

维护一种由数字构成字符数组，可以执行以下操作:
1.格式：l r c,将l~r都赋值为$c$
2.格式: l r d,询问l~r是否有长度为$d$的循环节
solve

使用线段树去维护这个字符串哈希值。
关于怎样判断一个字符串 $s$ 有长度为 $d$ 的循环节，可以证明字符串 $s$ 有长度为 $d$ 的循环节等价于 $s[1...n-d]=s[d+1...n]$ ($s[l,r]$ 表示 $s$ 从 $l$ 到$r$ 的子串)。
使用线段树维护子串的哈希值，就可以完成以上比较了。
code

[code]#include#include#include#define int long long#define N 1000007using namespace std;struct Sigement{        string s;        int mod,pw[100007],seed,note[100007];        struct Tr{                int tag,value;        }tree[500007];        void init(){                int len=s.size();                pw[0]=1;                note[0]=1;                for(int i=1;i>k;        cin>>tr1.s;        tr1.seed=128;        tr1.mod=998244353;        tr1.init();        tr1.build(0,n-1,1);        tr2.s=tr1.s;        tr2.seed=131;        tr2.mod=1e9+7;        tr2.init();        tr2.build(0,n-1,1);        for(int i=1;i>op;                if(op==1){                        int l,r,c;                        cin>>l>>r>>c;                        tr1.update(0,n-1,l-1,r-1,c,1);                        tr2.update(0,n-1,l-1,r-1,c,1);                }else{                        int l,r,d;                        cin>>l>>r>>d;                        l--;                        r--;                        if(r-l+1==d){                                cout

收藏一下   不知道什么时候能用到