HackerEarth Zeus and Fibonacci problem solution

In this HackerEarth Zeus and Fibonacci problem solution, You are given an array A consisting of N integers. You have to process two types of queries on this array.

1. Type 1: Change the ith element to X
2. Type 2: Given l and r, calculate: Sigma(i=l,r)Sigma(j=i,r)Fib(Sigma(k=i,j) Ak)

HackerEarth Zeus and Fibonacci problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define maxn 100001

class Matrix 
{
    public:
    int N;
    int M[2][2];
    Matrix() {}

    Matrix(int _N) 
    {
        N = _N;
        memset(M, 0, sizeof M);
    }
};
Matrix EMP(2),ID(2), FIB(2);
void gen() 
{
    ID.M[0][0] = ID.M[1][1] = 1;
    FIB.M[1][1] = FIB.M[0][1] = FIB.M[1][0] = 1;
}

Matrix operator*(const Matrix &X, const Matrix &Y) 
{
    int N = X.N;
    Matrix Z(N);
    for (int i = 0; i < N; i++) 
    {
        for (int j = 0; j < N; j++) 
        {
            for (int k = 0; k < N; k++) 
            {
                 Z.M[i][j] += (X.M[i][k] * 1LL * Y.M[k][j]) % mod;
                 if (Z.M[i][j] >= mod)
                  Z.M[i][j] -= mod;
            }
        }
    }
  return Z;
}
Matrix operator^(Matrix X, ll power)
{
    Matrix res = ID;
    while (power)
    {
         if (power & 1) 
         res = res * X;
         X = X * X;
         power >>= 1;
    }
     return res;
}
Matrix operator+(Matrix X, const Matrix &Y) 
{
    for (int i = 0; i < X.N; i++) 
    {
        for (int j = 0; j < X.N; j++) 
        {
             X.M[i][j] = (X.M[i][j] + Y.M[i][j]);
             if (X.M[i][j] >= mod) X.M[i][j] -= mod;
        }
    }
    return X;
}
// fib(0)=0 fib(1)=1
// to calculate fib(n) take mat^(n)
ll arr[maxn];
Matrix ans[4*maxn],pre[4*maxn],suff[4*maxn],sum[4*maxn];


void build(ll node,ll a,ll b)
{
    if(a==b)
    {
        ans[node]=FIB^(arr[a]);
        pre[node]=FIB^(arr[a]);
        suff[node]=FIB^(arr[a]);
        sum[node]=FIB^(arr[a]);
        return;
    }
    ll mid=(a+b)/2;
    build(2*node,a,mid);
    build(2*node+1,mid+1,b);
    
    pre[node]=pre[2*node];
    pre[node]=(pre[node]+(sum[2*node]*pre[2*node+1]));

    suff[node]=suff[2*node+1];
    suff[node]=(suff[node]+(sum[2*node+1]*suff[2*node]));

    sum[node]=sum[2*node]*sum[2*node+1];

    ans[node]=ans[2*node]+ans[2*node+1];
    ans[node]=(ans[node]+(suff[2*node]*pre[2*node+1]));
}
void update(ll node,ll a,ll b,ll ind,ll val)
{
    if(a>b || a>ind || b<ind)
    return;
    if(a==b)
    {
        ans[node]=FIB^val;
        pre[node]=FIB^val;
        suff[node]=FIB^val;
        sum[node]=FIB^val;
        return;
    }
    ll mid=(a+b)/2;
    if(ind<=mid)
    update(2*node,a,mid,ind,val);
    else
    update(2*node+1,mid+1,b,ind,val);

    pre[node]=pre[2*node];
    pre[node]=(pre[node]+(sum[2*node]*pre[2*node+1]));

    suff[node]=suff[2*node+1];
    suff[node]=(suff[node]+(sum[2*node+1]*suff[2*node]));

    sum[node]=sum[2*node]*sum[2*node+1];

    ans[node]=ans[2*node]+ans[2*node+1];
    ans[node]=(ans[node]+(suff[2*node]*pre[2*node+1]));
}
pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > query(ll node,ll a,ll b,ll l,ll r)
{
    if(a>b || a>r || b<l)
    assert(false);
    if(a>=l && b<=r)
    return {{ans[node],sum[node]},{pre[node],suff[node]}};

    ll mid=(a+b)/2;

    if(mid<l)return query(2*node+1,mid+1,b,l,r);
    else if(mid+1>r)return query(2*node,a,mid,l,r);
    
    pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > p1=query(2*node,a,mid,l,r);
    pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > p2=query(2*node+1,mid+1,b,l,r);
    pair<pair<Matrix,Matrix>,pair<Matrix,Matrix> > p;

    p.S.F=p1.S.F;
    p.S.F=(p.S.F+(p1.F.S*p2.S.F));

    p.S.S=p2.S.S;
    p.S.S=(p.S.S+(p2.F.S*p1.S.S));

    p.F.S=p1.F.S*p2.F.S;

    p.F.F=p1.F.F+p2.F.F;
    p.F.F=(p.F.F+(p1.S.S*p2.S.F));

    return p;

}
int main()
{
    boost1;boost2;  
    ll i,j,n,q,l,r,type,val,ind;
    cin>>n;
    assert(1<=n&&n<=100000);
    gen();
    for(i=1;i<=n;i++){
    cin>>arr[i];
    assert(1<=arr[i]&&arr[i]<=1000000000);
    }
    
    build(1,1,n);
    cin>>q;
    assert(1<=q&&q<=100000);
    while(q--)
    {
        cin>>type;
        assert(type==1||type==2);
        if(type==1)
        {
            cin>>ind>>val;
            assert(1<=ind&&ind<=n);
            assert(1<=val&&val<=1000000000);
            update(1,1,n,ind,val);
        }
        else
        {
            cin>>l>>r;
            assert(l<=r&&1<=l&&l<=n&&1<=r&&r<=n);
            Matrix temp=query(1,1,n,l,r).F.F;
            assert(0<=((temp.M[0][1])%mod)&&((temp.M[0][1])%mod)<mod);
            cout<<(temp.M[0][1])%mod<<endl;
        }
    }
    return 0;
}