线段维护矩阵乘法

#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e5+5;
struct Max{
    ll a[5][5];
    Max operator*(const Max &m){
        Max M;
        for(int i = 1; i <= 2; i++){
            for(int j = 1; j <= 2; j++){
                ll sum = 0;
                for(int k = 1; k <= 2; k++){
                    sum = (sum + this->a[i][k] * m.a[k][j] % mod) % mod;
                }
                M.a[i][j] = sum;
            }
        }
        return M;
    }
    Max(){
        this->a[1][1] = this->a[2][2] = 1;
        this->a[1][2] = this->a[2][1] = 0;
    }
};
struct Node{
    Max sum;
    int l;
    int r;
};
int n, m;
Node tree[4*maxn+5];
int cnt = 1;
void build(Node *tree, int now, int l, int r){
    tree[now].l = l;
    tree[now].r = r;
    if(tree[now].l == tree[now].r){
        //处理矩阵
        return;
    }
    int mid = (l + r) >> 1;
    build(tree, 2*now, l, mid);
    build(tree, 2*now+1, mid+1, r);
    tree[now].sum = tree[2*now].sum * tree[2*now+1].sum;
    return;
}
void updata(Node *tree, int now, int z, ll k, ll b){
    if(tree[now].l == tree[now].r){
        //处理矩阵
        return;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(z <= mid)    updata(tree, 2*now, z, k, b);
    else    updata(tree, 2*now+1, z, k, b);
    tree[now].sum = tree[2*now].sum * tree[2*now+1].sum;
    return;
}
Max query(Node *tree, int now, int l, int r){
    if(tree[now].l >= l && tree[now].r <= r)    return tree[now].sum;
    int mid = (tree[now].l + tree[now].r) >> 1;
    return (l <= mid? query(tree, 2*now, l, r): Max()) * (r > mid? query(tree, 2*now+1, l, r): Max());
}