一道“区间更新树状数组+标记永久化”的题目。被续了一天。
简单的说，该思想就是将树状数组“线段树化”，只不过还是建立在lowbit的基础上，复杂度和常数优秀，还挺好写的。
其实个人认为上面的题解写的很好，讲出了树状数组的精髓部分，将我以前有些疑惑的地方解决了一些。为什么是一些呢？还是因为有点懒而没有在某些点动笔算一算或画一画，只靠“感性理解”，这个标记永久化加在树状数组上也是一个非常妙的结合。
另一部分，对这道题来说，不止有树状数组，还有矩阵。
而这道题利用斐波那契数列的递推矩阵的对称性质将常数优化了许多，并经过一些等价命题，成功将题目转化成了可以写成可永久化的形式。否则按平常线段树会写的很长。
还有重要的一点——斐波那契的递推矩阵可逆，就可以用等比求和，求和式子里面的分母项可以放在最后一起处理。这也是能简化问题的关键。
不过还是太懒，写成了大常数。
Advertisements
