ABC331F，线段树代码查了好久都没查出问题，AC12WA13

#include<bits/stdc++.h>
#define N 1000005
#define ull unsigned long long
using namespace std;

struct node{
	int l,r;
	ull val1,val2;//正反hash值
}tmp,t[N<<2];
ull b[N];
char c,str[N];
int n,q,l,r,x,op;
void push_up(node &k,node ls,node rs){
	k.val1=ls.val1*b[rs.r-rs.l+1]+rs.val1;
	k.val2=ls.val2+rs.val2*b[ls.r-ls.l+1];
	return;
}
void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	if(l==r){
		t[x].val1=str[l];
		t[x].val2=str[l];
		return;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	push_up(t[x],t[x<<1],t[x<<1|1]);
	return;
}
void update(int x,int p,int c){
	int L=t[x].l;
	int R=t[x].r;
	if(L==R){
		t[x].val1=t[x].val2=c;
		return;
	}
	int mid=L+R>>1;
	update(x<<1|p>mid,p,c);
	push_up(t[x],t[x<<1],t[x<<1|1]);
	return;
}
node query(int x,int l,int r){
	int L=t[x].l;
	int R=t[x].r;
	if(l<=L&&R<=r)return t[x];
	int mid=L+R>>1;
	node ans;
	if(r<=mid)return query(x<<1,l,r);
	if(l>mid)return query(x<<1|1,l,r);
	push_up(ans,query(x<<1,l,r),query(x<<1|1,l,r));
	return ans;
}
int main(){
	scanf("%d%d %s",&n,&q,str+1);
	b[0]=1;
	for(int i=1;i<=n;i++)b[i]=b[i-1]*131;
	build(1,1,n);
	while(q--){
		scanf("%d",&op);
		if(op==1){
			scanf("%d %c",&x,&c);
			update(1,x,c);
		}else{
			scanf("%d%d",&l,&r);
			tmp=query(1,l,r);
			if(tmp.val1==tmp.val2)puts("Yes");
			else puts("No");
		}
	}
	return 0;
}