zkw线段树详细介绍（zkw线段树实现区间修改，区间查询最值） · znzryb

## 思路讲解

原来是想用zkw线段树写P1253，但是zkw写懒标记顺序不可调换的题目还是比较难的，我们要顺势而为，这个写zkw就是为了简单，写着反而复杂就干脆不写了。

参考讲解

[https://www.cnblogs.com/Judge/p/9514862.html](https://www.cnblogs.com/Judge/p/9514862.html)

[https://www.cnblogs.com/zsc985246/p/16112689.html](https://www.cnblogs.com/zsc985246/p/16112689.html)

![讲解没有细讲的zkw线段树求最大值转化方法](https://media.znzryb.com/20250404-15e2e31b/c370dd30-d5ad-4b7e-88e3-e248a3680253_693e4aae.png)



::: 参考这段建树程序

```cpp
inline void build(){
	for(M=1;M<=N;M<<=1);
	for(int i=M+1;i<=M+1+N;++i){
		cin>>tr[i];
	}
	for(int i=M-1;i;--i){
		tr[i]=max(tr[i<<1],tr[i<<1|1]);
		// 相当于子节点里装的值需要不断+母节点的值+母母节点的值+...+根节点的值
		// 才是真实的值，这样子可以比较好的实现bottom-up修改
		tr[i<<1]-=tr[i],tr[i<<1|1]-=tr[i];
	}
}
```


:::


这个线段树（求最大值的话）子节点里装的值需要不断+母节点的值+母母节点的值+...+根节点的值才是真实的值，这样子可以比较好的实现bottom-up修改。

![zkw线段树加法示意图](https://media.znzryb.com/20250404-15e2e31b/image_3c3d6296.png)

加法用这套东西是没有问题的，但容易发现，覆盖用这套操作会稍微有点问题。

[https://blog.csdn.net/weixin_43960287/article/details/108246164](https://blog.csdn.net/weixin_43960287/article/details/108246164)

![image](https://media.znzryb.com/20250404-15e2e31b/image_cf0556cf.png)

看过了，这个问题基本上可以说无解了。

## AC代码

## 心路历程（WA，TLE，MLE……）