|
|
Author |
hbghlyj
Post time 2023-7-14 12:26
本帖最后由 hbghlyj 于 2023-7-14 12:43 编辑
那么，线段树能做什么特别的事情？
画风突变
你以为你以为的就是我说的“加法”“求和”吗？
实际上我刚才说的树状数组加法，指的是交换群
设<$G,*$>是一个群，
若对任意\(a,b∈G\), \((a*b)*(a*b)=(a*a)*(b*b)\), 则\(G\)是交换群
实际上我刚才说的 线段树 求和，指的是幺半群
考虑 \(S\) 上的二元运算 \(*\)
若 存在单位元、满足结合律，则称为幺半群
（同时，如果还有\(S\)上的二元运算\(+\)，且\(*\)对\(+\)满足右分配律，还可以使用lazytag
具体来说，拿一些不常见的运算举个例子
定义 $a*b$ 为 $\max(a,b)$
显然 $a * b = b * a$ 满足交换律，
但由于 $*$ 对加法不满足 $a * ( b + c ) = ( a * b ) + ( a * c )$ [考虑 $a=3, b=2, c=2$.]
所以不能使用lazytag
对于单独的加法，单独的求$\max$，都可以使用树状数组，两者加在一起同时维护的话，不是不能用，但是效率会差一些
具体来说，拿一些不常见的运算举个例子
把“刷墙”看作一种运算 \(*\)
\[红色 * 蓝色 = 蓝色 \]
把蓝色的油漆涂在了（已经干了的）红色油漆上，就变成了蓝色
\[(红色 * 蓝色)* 白色 = 白色\]
在上面的基础上，又把墙刷白了
\[(红色 * 蓝色)* 白色 = 红色 * (蓝色* 白色)= 红色 * 白色 \]
很难说上式有什么物理意义，但在数学上是成立的
“刷墙”运算满足结合律，可以使用线段树。
但显然“刷墙”运算不满足交换律，不能使用树状数组。
西园一舍 到 西园一千舍，每个大舍有一千栋楼，每栋楼有一千个寝室
水电费都是数字，我们要进行的操作也只是查询加法、最大值等 |
|
大概讲一下，反正你们也不会听，哼~
