线段树模板带取模（建树+区间修改（加&乘）+区间查询）

转载https://cloud.tencent.com/developer/article/1089880

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+20;
const int mod=1e9+7;
int n,m;
struct node
{
    int mul,add,sum,l,r,siz;///mul乘法懒标记 add加法懒标记 sum区间和 siz区间长度
} T[4*N+1];

void update(int k)///更新父节点的值
{
    T[k].sum=(T[k*2].sum%mod+T[k*2+1].sum%mod)%mod;
}

void pushdown2(int a,int b)
{
    T[a].mul=(T[a].mul%mod*T[b].mul%mod)%mod;
    T[a].add=(T[a].add*T[b].mul)%mod;
    T[a].add=(T[a].add+T[b].add)%mod;
    T[a].sum=(T[a].sum%mod*T[b].mul%mod)%mod;
    T[a].sum=(T[a].sum+T[b].add%mod*T[a].siz)%mod;
}

void pushdown(int k)///懒标记下传
{
    if(T[k].add==0&&T[k].mul==1)
        return ;
    pushdown2(k*2,k);
    pushdown2(k*2+1,k);
    T[k].add=0;
    T[k].mul=1;
}

void build(int k,int ll,int rr)///建树
{
    T[k].l=ll;
    T[k].r=rr;
    T[k].siz=rr-ll+1;
    T[k].mul=1;
    if(ll==rr)
    {
        scanf("%d",&T[k].sum);
        return ;
    }
    int mid=(ll+rr)/2;
    build(k*2,ll,mid);
    build(k*2+1,mid+1,rr);
    update(k);
}

void mul_interval(int k,int ll,int rr,int val)///区间修改1 (l,r)的元素乘val
{
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        T[k].sum=(T[k].sum*val)%mod;
        T[k].mul=(T[k].mul*val)%mod;
        T[k].add=(T[k].add*val)%mod;
        return ;
    }
    pushdown(k);
    int mid=(T[k].l+T[k].r)/2;
    if(ll<=mid)
        mul_interval(k*2,ll,rr,val);
    if(rr>mid)
        mul_interval(k*2+1,ll,rr,val);
    update(k);
}

void add_interval(int k,int ll,int rr,int val)///区间修改2 (l,r)的元素加val
{
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        T[k].sum=(T[k].sum+T[k].siz*val)%mod;
        T[k].add=(T[k].add+val)%mod;
        return ;
    }
    pushdown(k);
    int mid=(T[k].l+T[k].r)/2;
    if(ll<=mid)
        add_interval(k*2,ll,rr,val);
    if(rr>mid)
        add_interval(k*2+1,ll,rr,val);
    update(k);
}

int ask_sum(int k,int ll,int rr)///区间查询 求(l,r)的和
{
    int ans=0;
    if(ll<=T[k].l&&T[k].r<=rr)
    {
        ans=(ans+T[k].sum)%mod;
        return ans;
    }
    pushdown(k);
    int mid=(T[k].l+T[k].r)/2;
    if(ll<=mid)
        ans=(ans+ask_sum(k*2,ll,rr))%mod;
    if(rr>mid)
        ans=(ans+ask_sum(k*2+1,ll,rr))%mod;
    return ans%mod;
}

int main()
{
    int t,k,n;
    scanf("%d",&t);
    while(t--)
    {
        memset(T,0,sizeof(T));
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--)
        {
            scanf("%d",&k);
            int a,b,val;
            if(k==1)///区间修改1 乘
            {
                scanf("%d%d%d",&a,&b,&val);
                mul_interval(1,a,b,val);
            }
            else if(k==2)///区间修改2 加
            {
                scanf("%d%d%d",&a,&b,&val);
                add_interval(1,a,b,val);
            }
            else if(k==3)///区间查询 求和
            {
                scanf("%d%d",&a,&b);
                int ans=ask_sum(1,a,b);
                cout<<ans<<'\n';
            }
            ///单点查询|单点修改时 使a==b代入函数
        }
    }
    return 0;
}