感觉自己做的麻烦了，但常数似乎不算差。（只是Luogu最慢的点不到2s本地要跑10+s）
感觉我的想法是最自然的，但不明白为什么网上似乎找不到这种做法。（不过当然所有的做法都是分类大讨论，而我的方法手算部分较为麻烦）
每次询问考虑每个位置的贡献，拆分成求所有长度<=R的区间的贡献次数和减去长度<L的区间贡献次数和。
分成两大类考虑，设当前考虑长度在[1,r]的所有区间，当前要计算数a[k]的贡献次数：
一： $2r\leq n$
1.$k\leq r$ 观察所有包含k的长度不超过r的区间，发现答案为$1+2+...+i+i+i+...i=\frac{1}{2}[(2r+1)i-i^2]$
2.$r<k<n-r+1$ 左右两边都可以延伸k的长度，于是答案为$1+2+...+r=\frac{r(r+1)}{2}$
3.$k\geq n-r+1$ 和情况一类似，答案为$1+2+...+(n-i)+(n-i)+(n-i)+...=\frac{1}{2}[2nr-n^2-n+2r+(2n-2r+1)i-i^2]$
二：$2r>n$
1.$k\leq n-r+1$观察发现和上面情况一是一样的：$\frac{1}{2}[(2r+1)i-i^2]$
2.$n-r+1<k<n/2$
答案为$1+2+...+i+i+...+i+(i-1)+(i-2)+...=\frac{1}{2}[2nr-n^2-r^2+r-n+(2n+n)i-2i^2]$
$n/2\leq k<r$
一波复杂的带入化简发现答案同上：$\frac{1}{2}[2nr-n^2-r^2+r-n+(2n+n)i-2i^2]$
3.$k\geq r$ 观察发现和上面情况三是一样的：$\frac{1}{2}[2nr-n^2-n+2r+(2n-2r+1)i-i^2]$
于是分别维护$\sum a_i$，$\sum a_i*i$，$\sum a_i*i^2$即可。
#include<cstdio>
#include<algorithm>
#define ls (x<<1)
#define rs (ls|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=1e9+,inv2=(mod+)/,inv6=(mod+)/;
int n,m,op,l,r,x,a[N]; int rd(){
int x=; char ch=getchar(); bool f=;
while (ch<'' || ch>'') f|=(ch=='-'),ch=getchar();
while (ch>='' && ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
return f ? -x : x;
} struct P{ int a[],tag; }v[N<<];
inline void inc(int &x,int y){ x+=y; (x>=mod)?x-=mod:; } P operator +(P a,P b){
inc(a.a[],b.a[]); inc(a.a[],b.a[]);
inc(a.a[],b.a[]); a.tag=; return a;
} int cal1(int x){ return 1ll*x*(x+)/%mod; }
int cal2(int x){ return 1ll*x*(x+)*(*x+)%mod*inv6%mod; } void put(int x,int L,int R,int k){
inc(v[x].a[],1ll*(R-L+)*k%mod);
inc(v[x].a[],1ll*(cal1(R)-cal1(L-)+mod)*k%mod);
inc(v[x].a[],1ll*(cal2(R)-cal2(L-)+mod)*k%mod);
inc(v[x].tag,k);
} void push(int x,int L,int R){
if (!v[x].tag) return;
int mid=(L+R)>>;
put(lson,v[x].tag); put(rson,v[x].tag); v[x].tag=;
} void build(int x,int L,int R){
if (L==R){
v[x].a[]=a[L]; v[x].a[]=1ll*a[L]*L%mod;
v[x].a[]=1ll*a[L]*L%mod*L%mod; return;
}
int mid=(L+R)>>;
build(lson); build(rson); v[x]=v[ls]+v[rs];
} void mdf(int x,int L,int R,int l,int r,int k){
if (L==l && r==R){ put(x,L,R,k); return; }
int mid=(L+R)>>; push(x,L,R);
if (r<=mid) mdf(lson,l,r,k);
else if (l>mid) mdf(rson,l,r,k);
else mdf(lson,l,mid,k),mdf(rson,mid+,r,k);
v[x]=v[ls]+v[rs];
} P que(int x,int L,int R,int l,int r){
if (L==l && r==R) return v[x];
int mid=(L+R)>>; push(x,L,R);
if (r<=mid) return que(lson,l,r);
else if (l>mid) return que(rson,l,r);
else return que(lson,l,mid)+que(rson,mid+,r);
} int Q1(int d,int r){
P t=que(,,n,,d);
return (1ll*t.a[]*(2ll*r+)%mod-t.a[]+mod)%mod*inv2%mod;
} int Q2(int d,int r){
if (d>n) return ;
P t=que(,,n,d,n);
return (((2ll*n*r-1ll*n*n-n+2ll*r)%mod*t.a[]%mod+(2ll*n-2ll*r+)%mod*t.a[]%mod-t.a[])%mod+mod)%mod*inv2%mod;
} int Q3(int L,int R,int r){
P t=que(,,n,L,R); return 1ll*r*(r+)/%mod*t.a[]%mod;
} int Q4(int L,int R,int r){
if (L>R) return ;
P t=que(,,n,L,R);
return (((2ll*n*r-1ll*n*n-1ll*r*r+r-n)%mod*t.a[]%mod+(2ll*n+)*t.a[]%mod-2ll*t.a[])%mod+mod)%mod*inv2%mod;
} int solve(int r){
if (!r) return ;
int L=min(r,n-r+),R=max(r,n-r+);
if (L==R) R++;
int r1=Q1(L,r),r2=Q2(R,r);
int r3=(L+<=R-)?((r<=n-r+)?Q3(L+,R-,r):Q4(L+,R-,r)):;
return (1ll*r1+r2+r3)%mod;
} int main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
n=rd(); m=rd();
rep(i,,n) a[i]=rd();
build(,,n);
while (m--){
op=rd(); l=rd(); r=rd();
if (l>r) swap(l,r);
if (op==) x=rd(),mdf(,,n,l,r,x);
else printf("%d\n",(solve(r)-solve(l-)+mod)%mod);
}
return ;
}