关于矩阵乘法和线段树递归顺序问题
查看原帖
关于矩阵乘法和线段树递归顺序问题
377760
Reunite楼主2023/10/1 10:41

我一开始认为,节点对应在线段树上的点维护的是它到重链链底的信息,这样的话,矩阵应该是从链底乘到链顶的。而又由于链顶的编号大,所以我线段树里面的顺序是反过来的,我觉得这很符合逻辑。但是实际证明,以下代码是可以通过的,但是用注释里面的实现却只有 30pts30pts,求说明或者指出我思路可能的错处。

void build(int u,int l,int r){
	if(l==r){
		t[u]=g[ti[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	t[u]=t[u<<1]*t[u<<1|1];
//	t[u]=t[u<<1|1]*t[u<<1];
	return ;
}

void updata(int u,int l,int r,int k,Matrix x){
	if(l==r){
		t[u]=x;
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid) updata(u<<1,l,mid,k,x);
	else updata(u<<1|1,mid+1,r,k,x);
	t[u]=t[u<<1]*t[u<<1|1];
//	t[u]=t[u<<1|1]*t[u<<1];
	return ;
}

Matrix query(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R) return t[u];
	int mid=(l+r)>>1;
	if(R<=mid) return query(u<<1,l,mid,L,R);
	if(L>mid) return query(u<<1|1,mid+1,r,L,R);
	return query(u<<1,l,mid,L,R)*query(u<<1|1,mid+1,r,L,R);
//	return query(u<<1|1,mid+1,r,L,R)*query(u<<1,l,mid,L,R);
}
2023/10/1 10:41
加载中...