浅谈数学性质与数据结构

发布时间 2023-09-26 16:15:00作者: 皮皮的橙子树

交换律:

当式子具有交换律时,我们可以考虑序列颠倒做两遍,算多了整体除二,强制钦定顺序等手段,优雅的解决这类问题。

https://codeforces.com/contest/1635/problem/F

 

结合律:

当发现维护的内容,存在结合律时,可以考虑线段树维护(需要支持信息快速结合),静态问题可以考虑猫树

 

重复消去律:

有时这点是不容易被察觉的,重复消去律可以支持 ST 表

 

维护顺序:

当需要维护顺序,或者当式子具有“有序优于乱序“”这个性质时,可以考虑可持久化权值线段树,版本差分,如果信息不能差分,可以考虑回滚莫队。

“预有序”数组的排序、插入、删除,通常都可以做到O(n)。