description
写个数据结构，支持区间加斐波那契数列和区间求和。
模 1e9+9。
solution
设 \(A=\begin{bmatrix}1&1 \\ 1 & 0 \end{bmatrix}\)。
则 \(\begin{bmatrix} F_{n+1}& F_{n} \end{bmatrix}=\begin{bmatrix}1&0 \end{bmatrix} \times A^n\)。
于是问题变成了区间加公比一定的等比数列。
对于区间 \([l,r]\)，如果要加上 \(A^p+A^{p+1}\dots +A^{p+r-l}\)，可以先提一个 \(A^{p-1}\) 出来，然后变成了 \(A^{p-1}\times(A^1+A^2+\dots+A^{r-l+1})\)。（矩阵乘法满足对矩阵加法的分配率）。
于是我们在线段树上维护每个节点加了的 \(A^{p-1}\) 的和 \(sum\)，询问求值的时候返回 \(sum\times (A^1+A^2+\dots+A^{r-l+1})\) 即可。
下传标记时，给左二子传 \(A^{tag}\)，右儿子传 \(A^{tag+mid-l+1}\)（显然这样的标记是满足可加性的）。
预处理矩阵幂次，时间复杂度 \(O((n+q)\log n)\)
hint
关键是把斐波那契数列转化成矩阵，找到合适的方法（满足标记可加）去维护区间。
2*2 的矩阵常数也不小，注意到 \(5\) 是模 1e9+9 下的二次剩余，可以先算出 \(\sqrt{5}\) ，然后用类似的办法维护（把矩阵换成斐波那契数列通项公式）。我的代码实现用的是矩阵。