선분 트 리 템 플 릿 모드 (트 리 만 들 기 + 구간 수정 (더하기 & 곱 하기) + 구간 조회)

3070 단어 데이터 구조
전재 하 다https://cloud.tencent.com/developer/article/1089880
#include 
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<

좋은 웹페이지 즐겨찾기