柒葉灬 的博客

柒葉灬 的博客

进阶倍增(个人笔记6)

posted on 2018-08-27 19:56:29 | under 技巧篇 |

倍增更深层一步理解。


  • 1.倍增如果理解透彻了,就可以看出来这就是一个小型线段树,把子树的信息收集上来,只不过不能支持在线修改而已,所以,他可以干很多线段树能干的事情。

  • 2.倍增不仅是求 区间max , 区间min 那么简单而已 , 有时候甚至可以直接倍增出!答案!。

举个栗子,“2951最优贸易简易版”,这道题目就很好的说明了什么是倍增出答案,答案无非是左边或者右边,或者是右边mx减去左边mn,所以ans倍增数组就能继续下去,(简直跟线段树一模一样)。


总结:倍增可以当做线段树使用。

END