用矩阵表示变化&&线段树维护矩阵
引入问题
- 已知一个数列
- 进行下面四种操作
- 1.区间赋值成 (x)
- 2.区间乘上一个数 (x)
- 3.区间加上一个数 (x)
- 4.求出区间每一个数的和
洛谷P3373 (只有后面三种操作)
矩阵入门
可以看看我写的这篇博客
正文
线段树维护的是带有结合律的东西
假如维护的东西不存在结合律
那么每次一个新的标记就会把旧的标记挤下去
每一个标记都要遍历整棵树，复杂度变成 (O(nm))
线段树维护矩阵
众所周知，矩阵乘法是有结合率的
即 :
(A(B C) = (AB)C)
那么我们可以在线段树的每一个节点维护一个矩阵来表示一些信息
那么我们的每一次操作都想方设法把它变成"乘上一个矩阵"
那么我们就可以线段树维护区间矩阵乘法，来表示一些结合律不是那么明显的信息
注意 : 由于矩阵乘法不具有交换律，所以我们每次只能左乘，或只能右乘一个转移矩阵
左乘 和 右乘 分别看个人实现的是一个列矩阵，还是一个行矩阵
矩阵模拟变化
每一个结点用矩阵可以表示成这样
[left[egin{array}{c}v\send{array}
ight]
]
(v) 表示维护的权值(区间和)，(s) 表示结点的大小
来按题目中的意思模拟
把原矩阵左乘一个矩阵来得到我们要的新矩阵
区间加 (x)
[left[egin{array}{c}1&x\0&1end{array}
ight] imesleft[egin{array}{c}v\send{array}
ight]=left[egin{array}{c}v + s imes x\send{array}
ight]
]
区间乘 (x)
[left[egin{array}{c}x&0\0&1end{array}
ight] imesleft[egin{array}{c}v\send{array}
ight]=left[egin{array}{c}v imes x\send{array}
ight]
]
区间赋值为 x
[left[egin{array}{c}0&x\0&1end{array}
ight] imesleft[egin{array}{c}v\send{array}
ight]=left[egin{array}{c}s imes x\send{array}
ight]
]
区间求和
即按普通的线段树那样
把每一个结点的矩阵加在一起即可
对了，最好写一个矩阵类，弄个矩阵乘法，加法之类的
由于矩阵运算有一个 (8) 的小常数，我吸氧后才勉强通过