线段树

支持修改区间加、区间乘、查询区间和的线段树结构体封装版 可以类比的写出其他操作

struct node
{
	int l,r,mid;
	long long d,lazyadd,lazymul;
};
struct tree
{
	node t[N*4];
	void build(int i,int l,int r)
	{
		t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
		t[i].d=t[i].lazyadd=0;t[i].lazymul=1;
		if(l==r)
		{
			t[i].d=a[l];
			return;
		}
		build(i<<1,l,t[i].mid);
		build(i<<1|1,t[i].mid+1,r);
		t[i].d=(t[i<<1].d+t[i<<1|1].d)%p;
		return;
	}
	void pushdown(int i)
	{
		if(!t[i].lazyadd&&t[i].lazymul==1) return;
		t[i<<1].d=(t[i<<1].d*t[i].lazymul+(t[i<<1].r-t[i<<1].l+1)*t[i].lazyadd)%p;
		t[i<<1].lazyadd=(t[i<<1].lazyadd*t[i].lazymul+t[i].lazyadd)%p;
		t[i<<1].lazymul=(t[i<<1].lazymul*t[i].lazymul)%p;
		t[i<<1|1].d=(t[i<<1|1].d*t[i].lazymul+(t[i<<1|1].r-t[i<<1|1].l+1)*t[i].lazyadd)%p;
		t[i<<1|1].lazyadd=(t[i<<1|1].lazyadd*t[i].lazymul+t[i].lazyadd)%p;
		t[i<<1|1].lazymul=(t[i<<1|1].lazymul*t[i].lazymul)%p;
		t[i].lazyadd=0;t[i].lazymul=1;
		return; 
	}
	void modify_add(int i,int l,int r,long long k)
	{
		if(l<=t[i].l&&t[i].r<=r)
		{
			t[i].d=(t[i].d+(t[i].r-t[i].l+1)*k)%p;
			t[i].lazyadd=(t[i].lazyadd+k)%p;
			return;
		}
		pushdown(i);
		if(l<=t[i].mid) modify_add(i<<1,l,r,k);
		if(t[i].mid+1<=r) modify_add(i<<1|1,l,r,k);
		t[i].d=(t[i<<1].d+t[i<<1|1].d)%p;
		return; 
	}
	void modify_mul(int i,int l,int r,long long k)
	{
		if(l<=t[i].l&&t[i].r<=r)
		{
			t[i].d=(t[i].d*k)%p;
			t[i].lazymul=(t[i].lazymul*k)%p;
			t[i].lazyadd=(t[i].lazyadd*k)%p;
			return;
		}
		pushdown(i);
		if(l<=t[i].mid) modify_mul(i<<1,l,r,k);
		if(t[i].mid+1<=r) modify_mul(i<<1|1,l,r,k);
		t[i].d=(t[i<<1].d+t[i<<1|1].d)%p;
		return;
	}
	long long query(int i,int l,int r)
	{
		if(l<=t[i].l&&t[i].r<=r)
		{
			return t[i].d;
		}
		pushdown(i);
		long long res=0;
		if(l<=t[i].mid) res=(res+query(i<<1,l,r))%p;
		if(t[i].mid+1<=r) res=(res+query(i<<1|1,l,r))%p;
		return res;
	}
}t;