虽然用的是一种十分另类的树状数组。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdarg.h>
#include<ctype.h>
#define lowbit(e) (e&(-e))
typedef long long ll;
int n,ch,t,g,m;
ll p,c;
typedef struct
{
	ll sum,zhi,chen,lzy;
}hh;
hh a[100005];
void add(int w,int l)
{
	a[l].sum=w%p;a[l].chen=1;
	int r=lowbit(l);
	for (int x=1;x<r;x<<=1)
		a[l].sum=(a[l].sum+a[l-x].sum)%p;
}
void pushdown(int w)
{
	int up=lowbit(w);
	if (w>1)
	{
		for (int x=1;x<up;x<<=1)
		{
			int f=lowbit((w-x));
			a[w-x].sum=(a[w-x].sum*a[w].chen+a[w].lzy*f)%p;
			a[w-x].zhi=(a[w-x].zhi*a[w].chen+a[w].lzy)%p;
			a[w-x].lzy=(a[w-x].lzy*a[w].chen+a[w].lzy)%p;
			a[w-x].chen=(a[w-x].chen*a[w].chen)%p;
		}
		a[w].lzy=0;a[w].chen=1;
	}
}
ll cheng(ll w,int l,int r,int e)
{
	int left=e-lowbit(e)+1,up=lowbit(e);
	if (left>r||e<l)
	{
		return a[e].sum;
	}
	if (left>=l&&e<=r)
	{
		a[e].sum=(a[e].sum*w)%p;
		a[e].zhi=(a[e].zhi*w)%p;
		a[e].chen=(a[e].chen*w)%p;
		a[e].lzy=(a[e].lzy*w)%p;
		return a[e].sum;
	}
	pushdown(e);
	if (e>=l&&e<=r)
		a[e].zhi=(a[e].zhi*w)%p;
	a[e].sum=a[e].zhi;
	for (int x=1;x<up;x<<=1)
	{
		a[e].sum+=cheng(w,l,r,e-x);
		a[e].sum%=p;
	}
	return a[e].sum;
}
ll insert(ll w,int l,int r,int e)
{
	int left=e-lowbit(e)+1,up=lowbit(e);
	if (left>r||e<l)
	{
		return a[e].sum;
	}
	if (left>=l&&e<=r)
	{
		a[e].sum=(a[e].sum+(e-left+1)*w)%p;
		a[e].zhi=(a[e].zhi+w)%p;
		a[e].lzy=(a[e].lzy+w)%p;
		return a[e].sum;
	}
	pushdown(e);
	if (e>=l&&e<=r)
		a[e].zhi=(a[e].zhi+w)%p;
	a[e].sum=a[e].zhi;
	for (int x=1;x<up;x<<=1)
	{
		a[e].sum+=insert(w,l,r,e-x);
		a[e].sum%=p;
	}
	return a[e].sum;
}
ll query(int l,int r,int e)
{
	int left=e-lowbit(e)+1,up=lowbit(e);
	if (left>r||e<l)
	{
		return 0;
	}
	if (left>=l&&e<=r)
	{
		return a[e].sum;
	}
	pushdown(e);
	ll summ=0;
	if (e>=l&&e<=r)
		summ+=a[e].zhi;
	for (int x=1;x<up;x<<=1)
	{
		summ+=query(l,r,e-x);
		summ%=p;
	}
	return summ;
}
int main(void)
{
	scanf("%d%lld",&n,&p);
	for (int x=1;x<=n;x++)
	{
		scanf("%lld",&a[x].zhi);
		add(a[x].zhi,x);
	}
	scanf("%d",&m);
	for (int x=1;x<=m;x++)
	{
		scanf("%d%d%d",&ch,&t,&g);
		if (ch==1)
		{
			scanf("%lld",&c);
			for (int y=n;y>0;y-=lowbit(y))
				cheng(c,t,g,y);
		}
		else if (ch==2)
		{
			scanf("%lld",&c);
			for (int y=n;y>0;y-=lowbit(y))
				insert(c,t,g,y);
		}
		else if (ch==3)
		{
			ll summ=0;
			for (int y=n;y>0;y-=lowbit(y))
				summ=(summ+query(t,g,y))%p;
			printf("%lld\n",summ);
		}
	}
	return 0;
}

其实它只是运用了树状数组的lowbit来设结点，实质上是和线段树相似的。 详见https://www.luogu.com.cn/blog/westernhan/shu-zhuang-shuo-zu-di-xin-gou-xiang